Các thành phần được kết nối mạnh mẽ

Mục lục

Thuật toán Kosaraju
Ví dụ về Python, Java, C ++
Độ phức tạp của thuật toán Kosaraju
Các ứng dụng thành phần được kết nối mạnh mẽ

Trong hướng dẫn này, bạn sẽ tìm hiểu cách các thành phần được kết nối mạnh mẽ được hình thành. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của thuật toán kosararju trong C, C ++, Java và Python.

Thành phần được kết nối mạnh mẽ là phần của đồ thị có hướng trong đó có một đường đi từ mỗi đỉnh đến một đỉnh khác. Nó chỉ có thể áp dụng trên một đồ thị có hướng .

Ví dụ:

Hãy để chúng tôi lấy đồ thị dưới đây.

Đồ thị ban đầu

Các thành phần được liên kết chặt chẽ của biểu đồ trên là:

Các thành phần được kết nối mạnh mẽ

Bạn có thể quan sát thấy rằng trong thành phần được kết nối mạnh đầu tiên, mọi đỉnh đều có thể đến đỉnh khác thông qua đường dẫn được định hướng.

Các thành phần này có thể được tìm thấy bằng Thuật toán Kosaraju .

Thuật toán Kosaraju

Thuật toán Kosaraju dựa trên thuật toán tìm kiếm theo chiều sâu được triển khai hai lần.

Có ba bước.

Thực hiện tìm kiếm độ sâu đầu tiên trên toàn bộ đồ thị.
Chúng ta hãy bắt đầu từ đỉnh-0, thăm tất cả các đỉnh con của nó và đánh dấu các đỉnh đã thăm là xong. Nếu một đỉnh dẫn đến một đỉnh đã được thăm, thì hãy đẩy đỉnh này vào ngăn xếp.
Ví dụ: Bắt đầu từ đỉnh-0, đi đến đỉnh-1, đỉnh-2, và sau đó đến đỉnh-3. Đỉnh-3 dẫn đến đỉnh-0 đã được thăm, vì vậy hãy đẩy đỉnh nguồn (tức là đỉnh-3) vào ngăn xếp. DFS trên đồ thị
Đi tới đỉnh trước (đỉnh-2) và thăm các đỉnh con của nó tức là đỉnh-4, đỉnh-5, đỉnh-6 và đỉnh-7 một cách tuần tự. Vì không có điểm nào để đi từ đỉnh-7, hãy đẩy nó vào ngăn xếp. DFS trên biểu đồ
Đi đến đỉnh trước (đỉnh-6) và thăm các đỉnh con của nó. Tuy nhiên, tất cả các đỉnh con của nó đều được thăm, vì vậy hãy đẩy nó vào ngăn xếp. Xếp chồng
Tương tự, một ngăn xếp cuối cùng được tạo. Ngăn xếp cuối cùng
Đảo ngược đồ thị ban đầu. DFS trên đồ thị đảo ngược
Thực hiện tìm kiếm theo chiều sâu trên biểu đồ đảo ngược.
Bắt đầu từ đỉnh trên cùng của ngăn xếp. Đi qua tất cả các đỉnh con của nó. Khi đạt đến đỉnh đã được thăm, một thành phần được kết nối mạnh mẽ sẽ được hình thành.
Ví dụ: Bật đỉnh-0 từ ngăn xếp. Bắt đầu từ đỉnh-0, đi qua các đỉnh con của nó (đỉnh-0, đỉnh-1, đỉnh-2, đỉnh-3 theo thứ tự) và đánh dấu chúng là đã thăm. Con của đỉnh-3 đã được thăm, vì vậy các đỉnh được thăm này tạo thành một thành phần được kết nối mạnh mẽ. Bắt đầu từ đỉnh và đi qua tất cả các đỉnh
Đi đến ngăn xếp và bật đỉnh trên cùng nếu đã được truy cập. Nếu không, hãy chọn đỉnh trên cùng từ ngăn xếp và đi qua các đỉnh con của nó như đã trình bày ở trên. Bật đỉnh trên cùng nếu đã được truy cập Thành phần được kết nối mạnh mẽ
Do đó, các thành phần kết nối mạnh mẽ bao gồm: Tất cả các thành phần kết nối mạnh mẽ

Ví dụ về Python, Java, C ++

Python Java C ++

 # 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()

 // Kosaraju's algorithm to find strongly connected components in Java import java.util.*; import java.util.LinkedList; class Graph ( private int V; private LinkedList 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 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 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 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(); ) )

 // Kosaraju's algorithm to find strongly connected components in C++ #include #include #include using namespace std; class Graph ( int V; list *adj; void fillOrder(int s, bool visitedV(), stack &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(V); ) // DFS void Graph::DFS(int s, bool visitedV()) ( visitedV(s) = true; cout << s << " "; list::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::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 &Stack) ( visitedV(s) = true; list::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 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:"; g.printSCC(); )