# 強連通的組件 > 原文： [https://www.programiz.com/dsa/strongly-connected-components](https://www.programiz.com/dsa/strongly-connected-components) #### 在本教程中，您將學習如何形成強連通的組件。 此外，您還將在 C，C++ ，Java 和 Python 中找到 kosararju 算法的工作示例。 強連通的組件是有向圖的一部分，其中從每個頂點到另一個頂點都有一條路徑。 僅適用于[**有向圖**](/dsa/graph)。 例如： 讓我們來看看下圖。  初始的圖 上圖的強連通的組件是：  強連通組件 您可以觀察到，在第一個強連接的組件中，每個頂點都可以通過定向路徑到達另一個頂點。 可以使用 **Kosaraju 算法**找到這些組件。 * * * ## Kosaraju 算法 Kosaraju 算法基于[兩次實現的深度優先搜索算法](/dsa/graph-dfs)。 涉及三個步驟。 1. 在整個圖上執行深度優先搜索。 讓我們從頂點 0 開始，訪問其所有子頂點，并將訪問的頂點標記為完成。 如果頂點通向已經訪問過的頂點，則將該頂點推入棧。 例如：從頂點 0 開始，轉到頂點 1，頂點 2，然后到達頂點 3。 頂點 3 導致已經訪問過的頂點 0，因此將源頂點（即頂點 3）壓入棧。  圖上的 DFS 轉到上一個頂點（頂點 2），并訪問其子頂點，即頂點 4，頂點 5，頂點 6 和頂點 7 順序。 由于頂點 7 無處可去，因此將其推入棧。  圖上的 DFS 轉到上一個頂點（頂點 6），并訪問其子頂點。 但是，它的所有子頂點都已訪問，因此將其推入棧。  堆疊 類似地，創建最終堆疊。  最終籌碼 2. 反轉原始圖。  反轉圖上的 DFS 3. 對反向圖執行深度優先搜索。 從棧的頂部頂點開始。 遍歷其所有子頂點。 一旦到達已經訪問過的頂點，就會形成一個強連通的組件。 例如：從棧中彈出頂點 0。 從頂點 0 開始，遍歷其子頂點（依次為頂點 0，頂點 1，頂點 2，頂點 3）并將它們標記為已訪問。 頂點 3 的子級已經被訪問過，因此這些訪問過的頂點形成一個強連接的組件。  從頂部開始，并遍歷所有頂點 轉到棧并彈出頂部頂點（如果已訪問）。 否則，請從棧中選擇頂部頂點，然后遍歷其子頂點，如上所示。  如果已經訪問過，則彈出頂部頂點  強連通的組件 4. 因此，強連接的組件為：  所有強連接的組件 * * * ## Python，Java，C++ 示例 ```py # Kosaraju's algorithm to find strongly connected components in Python from collections import defaultdict class Graph: def __init__(self, vertex): self.V = vertex self.graph = defaultdict(list) # Add edge into the graph def add_edge(self, s, d): self.graph[s].append(d) # dfs def dfs(self, d, visited_vertex): visited_vertex[d] = True print(d, end='') for i in self.graph[d]: if not visited_vertex[i]: self.dfs(i, visited_vertex) def fill_order(self, d, visited_vertex, stack): visited_vertex[d] = True for i in self.graph[d]: if not visited_vertex[i]: self.fill_order(i, visited_vertex, stack) stack = stack.append(d) # transpose the matrix def transpose(self): g = Graph(self.V) for i in self.graph: for j in self.graph[i]: g.add_edge(j, i) return g # Print stongly connected components def print_scc(self): stack = [] visited_vertex = [False] * (self.V) for i in range(self.V): if not visited_vertex[i]: self.fill_order(i, visited_vertex, stack) gr = self.transpose() visited_vertex = [False] * (self.V) while stack: i = stack.pop() if not visited_vertex[i]: gr.dfs(i, visited_vertex) print("") g = Graph(8) g.add_edge(0, 1) g.add_edge(1, 2) g.add_edge(2, 3) g.add_edge(2, 4) g.add_edge(3, 0) g.add_edge(4, 5) g.add_edge(5, 6) g.add_edge(6, 4) g.add_edge(6, 7) print("Strongly Connected Components:") g.print_scc() ``` ```java // Kosaraju's algorithm to find strongly connected components in Java import java.util.*; import java.util.LinkedList; class Graph { private int V; private LinkedList<Integer> adj[]; // Create a graph Graph(int s) { V = s; adj = new LinkedList[s]; for (int i = 0; i < s; ++i) adj[i] = new LinkedList(); } // Add edge void addEdge(int s, int d) { adj[s].add(d); } // DFS void DFSUtil(int s, boolean visitedVertices[]) { visitedVertices[s] = true; System.out.print(s + " "); int n; Iterator<Integer> i = adj[s].iterator(); while (i.hasNext()) { n = i.next(); if (!visitedVertices[n]) DFSUtil(n, visitedVertices); } } // Transpose the graph Graph Transpose() { Graph g = new Graph(V); for (int s = 0; s < V; s++) { Iterator<Integer> i = adj[s].listIterator(); while (i.hasNext()) g.adj[i.next()].add(s); } return g; } void fillOrder(int s, boolean visitedVertices[], Stack stack) { visitedVertices[s] = true; Iterator<Integer> i = adj[s].iterator(); while (i.hasNext()) { int n = i.next(); if (!visitedVertices[n]) fillOrder(n, visitedVertices, stack); } stack.push(new Integer(s)); } // Print strongly connected component void printSCC() { Stack stack = new Stack(); boolean visitedVertices[] = new boolean[V]; for (int i = 0; i < V; i++) visitedVertices[i] = false; for (int i = 0; i < V; i++) if (visitedVertices[i] == false) fillOrder(i, visitedVertices, stack); Graph gr = Transpose(); for (int i = 0; i < V; i++) visitedVertices[i] = false; while (stack.empty() == false) { int s = (int) stack.pop(); if (visitedVertices[s] == false) { gr.DFSUtil(s, visitedVertices); System.out.println(); } } } public static void main(String args[]) { Graph g = new Graph(8); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 3); g.addEdge(2, 4); g.addEdge(3, 0); g.addEdge(4, 5); g.addEdge(5, 6); g.addEdge(6, 4); g.addEdge(6, 7); System.out.println("Strongly Connected Components:"); g.printSCC(); } } ``` ```cpp // Kosaraju's algorithm to find strongly connected components in C++ #include <iostream> #include <list> #include <stack> using namespace std; class Graph { int V; list<int> *adj; void fillOrder(int s, bool visitedV[], stack<int> &Stack); void DFS(int s, bool visitedV[]); public: Graph(int V); void addEdge(int s, int d); void printSCC(); Graph transpose(); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } // DFS void Graph::DFS(int s, bool visitedV[]) { visitedV[s] = true; cout << s << " "; list<int>::iterator i; for (i = adj[s].begin(); i != adj[s].end(); ++i) if (!visitedV[*i]) DFS(*i, visitedV); } // Transpose Graph Graph::transpose() { Graph g(V); for (int s = 0; s < V; s++) { list<int>::iterator i; for (i = adj[s].begin(); i != adj[s].end(); ++i) { g.adj[*i].push_back(s); } } return g; } // Add edge into the graph void Graph::addEdge(int s, int d) { adj[s].push_back(d); } void Graph::fillOrder(int s, bool visitedV[], stack<int> &Stack) { visitedV[s] = true; list<int>::iterator i; for (i = adj[s].begin(); i != adj[s].end(); ++i) if (!visitedV[*i]) fillOrder(*i, visitedV, Stack); Stack.push(s); } // Print strongly connected component void Graph::printSCC() { stack<int> Stack; bool *visitedV = new bool[V]; for (int i = 0; i < V; i++) visitedV[i] = false; for (int i = 0; i < V; i++) if (visitedV[i] == false) fillOrder(i, visitedV, Stack); Graph gr = transpose(); for (int i = 0; i < V; i++) visitedV[i] = false; while (Stack.empty() == false) { int s = Stack.top(); Stack.pop(); if (visitedV[s] == false) { gr.DFS(s, visitedV); cout << endl; } } } int main() { Graph g(8); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 3); g.addEdge(2, 4); g.addEdge(3, 0); g.addEdge(4, 5); g.addEdge(5, 6); g.addEdge(6, 4); g.addEdge(6, 7); cout << "Strongly Connected Components:\n"; g.printSCC(); } ``` * * * ## Kosaraju 算法復雜度 Kosaraju 算法在線性時間即`O(V+E)`中運行。 * * * ## 強連通的組件應用 * 車輛路線選擇應用 * 地圖 * 形式驗證中的模型檢查