Задача про граф, Проверить является ли граф связным Опции

[-inferno-]

помогите решить следующую задачу:
Есть граф заданный матрицей смежности, необходимо проверить является ли он связным.

[Altair]

Используем модифицированный алгоритм Флойда - алгоритм Уоршалла.
Или транзитивное замыкание матрицы.
Вход - булева матрица смежности,
(1 есть ребро 0 нету)

как и в алгоритме флойда
каждый элемент матрицы вычисляется по формуле, для данного случая такой:
Ak[i,j]=Ak-1[i,j] or (Ak-1[i,k] and Ak-1[k,j])

В результате получим матрицу, и надо будет проверить ее на наличие нулевых элементов, если нету то граф связан.

Можно использовать и прямо алгоритм Флойда... алгоритмическая сложность одна и та же...
Тогда для проверки на связанность надо будет проверить нет ли в результате бесконечных путей.