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

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

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