В чем отличие поиска компонент связности в ориентированных и неориентированных графах?

Отличие поиска компонент связности в ориентированных и неориентированных графах заключается в используемых понятиях и алгоритмах:

• Для неориентированных графов общее понятие связности распространяется, и для поиска компонент связности используется обычный обход в глубину (DFS) практически без модификаций. brestprog.by ru.algorithmica.org При запуске обхода из одной вершины он гарантированно посетит все вершины, до которых возможно добраться, то есть всю компоненту связности, к которой принадлежит начальная вершина. brestprog.by Для нахождения всех компонент нужно запустить обход из каждой вершины по очереди, если ещё не обошли её компоненту ранее. brestprog.by

• Для ориентированных графов вместо понятия связности используются понятия слабой и сильной связности. neerc.ifmo.ru Компонентой сильной связности называется класс эквивалентности множества вершин этого графа относительно сильной связности. neerc.ifmo.ru Компоненты сильной связности могут быть найдены с помощью обхода в глубину. neerc.ifmo.ru Например, для этого используется алгоритм Косарайю, который состоит из трёх шагов: выполнить поиск в глубину (DFS), пока не будут «помечены» все вершины, инвертировать исходный граф и выполнить DFS в порядке убывания пометок вершин. {8-host} Полученные деревья каждого такта DFS последнего шага являются компонентами сильной связности. {8-host}