Нахождение транзитивного замыкания графа

Я пытаюсь вычислить транзитивное замыкание графа. Рассмотрим этот граф в качестве примера (на картинке изображен граф, его матрица смежности и связности): введите описание изображения здесь

Используя алгоритм Варшалла, который я нашел на этой странице, я генерирую эту матрицу связи (= транзитивное замыкание?), отличное от показанного на картинке:

 01111
 01111
 01011
 01111
 01111

Я также пробовал использовать этот апплет, который также дает мне другой результат:

01111
01111
01111
01111
01111

Так что я сейчас немного запутался, так как не знаю, какая матрица правильная. Может кто-нибудь пролить свет на мою проблему?


transitive-closure transitive-closure-table
person TheAptKid    schedule 18.11.2012    source источник

Ответы (1)


arrow_upward
2
arrow_downward

C (1,1): буква T в точке C (1,1) означает, что на диагонали A. должно быть Ts.

C (3,3): Кажется, что только один раунд алгоритма Уоршалла находит достижимые узлы на глубине двух. Поскольку для достижения третьего узла требуется три ребра, одного раунда недостаточно.

person andyn    schedule 18.11.2012
comment
Спасибо. Я запустил алгоритм на выходе первой итерации и получил результат, который совпадает с результатом апплета. Однако у меня есть еще два вопроса: 1) Прав ли я, если говорю, что я должен запустить алгоритм n-1 раз, чтобы сгенерировать транзитивное замыкание? 2) У каждого графа будет T на диагонали матрицы (каждый узел может перейти к самому себе за 0 шагов)? - person TheAptKid; 18.11.2012
comment
1) Достаточно N-1 раз. 2) Если вы посмотрите на график, просто нет способа добраться до узла 1 из других узлов, кроме самого узла. Наличие узлов по диагонали означает, что узлы доступны сами по себе. - person andyn; 18.11.2012