Найдите компоненты слабой связи в ориентированном графе

Слабосвязный граф:

Ориентированный граф ' G = (V, E)' называется слабосвязным , если лежащий в его основе неориентированный граф M связен.

The underlying undirected graph is the graph Ĝ = (V, Ê) where Ê represents the set of undirected edges that is obtained by removing the arrowheads from the directed edges and making them bidirectional in G.

Пример:

The directed graph G above is weakly connected since its underlying undirected graph Ĝ is connected.

Компонент слабой связи:

Для ориентированного графа компонент слабой связности (WCC) — это подграф исходного графа, в котором все вершины соединены друг с другом некоторым путем, игнорируя направление ребер.

Example:

In the above directed graph, there are two weakly connected components:

• [0, 1, 2, 3]
• [4, 5]

Алгоритм поиска компонента слабой связности:

Он использует алгоритм для поиска компонентов связности неориентированного графа.

• Постройте базовый неориентированный граф данного ориентированного графа.
• Найдите все компоненты связности неориентированного графа.
• Связные компоненты неориентированного графа будут слабосвязными компонентами ориентированного графа.

Реализация:

Ниже приведен код слабосвязного компонента , который принимает ориентированный граф DG в качестве входных данных и возвращает все слабосвязные компоненты WCC входного графа.

Временная сложность: O(V+E)