148
правок
Изменения
Нет описания правки
[[Категория: Обход в глубину]]
==Алгоритм==
[[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связанности]] можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину]] в 3 этапа:
Значит, из случая а) и не существования случая б) получаем, что вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы в обоих графах.
}}
==Время работы алгоритма==
#Для того, чтобы инвертировать все ребра в графе, представленном в виде списка потребуется <tex>O(V + E)</tex> действий. Для матричного представления графа ненужно выполнять никакие действия для его инвертирования.
#Количество ребер в инвертированном равно количеству ребер в изначальном графе, поэтому поиск в глубину будет работать за <tex>O(V + E)</tex>
#Поиск в глубину в исходном графе выполняется за <tex>O(V + E)</tex>.
В итоге получаем, что время работы алгоритма <tex>O(V + E)</tex>.
==Пример реализации==
