Silnie połączone komponenty

Spisie treści

Algorytm Kosaraju
Przykłady w Pythonie, Javie, C ++
Złożoność algorytmu Kosaraju
Silnie połączone aplikacje komponentów

W tym samouczku nauczysz się, jak silnie połączone komponenty są tworzone. Znajdziesz również działające przykłady algorytmu kosararju w językach C, C ++, Java i Python.

Silnie powiązany komponent to część ukierunkowanego wykresu, w której znajduje się ścieżka od każdego wierzchołka do innego wierzchołka. Ma zastosowanie tylko na wykresie skierowanym .

Na przykład:

Spójrzmy na poniższy wykres.

Wykres początkowy

Silnie powiązane elementy powyższego wykresu to:

Silnie połączone komponenty

Można zauważyć, że w pierwszym silnie połączonym komponencie każdy wierzchołek może dotrzeć do drugiego wierzchołka poprzez skierowaną ścieżkę.

Te komponenty można znaleźć za pomocą algorytmu Kosaraju .

Algorytm Kosaraju

Algorytm Kosaraju jest oparty na algorytmie przeszukiwania w pierwszej kolejności zaimplementowanym dwukrotnie.

Wymagane są trzy kroki.

Przeprowadź najpierw wyszukiwanie głębokości na całym wykresie.
Zacznijmy od wierzchołka-0, odwiedźmy wszystkie jego wierzchołki potomne i zaznaczmy odwiedzone wierzchołki jako gotowe. Jeśli wierzchołek prowadzi do już odwiedzonego wierzchołka, wsuń ten wierzchołek do stosu.
Na przykład: Zaczynając od wierzchołka-0, przejdź do wierzchołka-1, wierzchołka-2, a następnie do wierzchołka-3. Vertex-3 prowadzi do już odwiedzonego wierzchołka-0, więc wsuń wierzchołek źródłowy (tj. Wierzchołek-3) do stosu. DFS na wykresie
Przejdź do poprzedniego wierzchołka (wierzchołek-2) i odwiedź jego wierzchołki potomne, tj. Wierzchołek-4, wierzchołek-5, wierzchołek-6 i wierzchołek-7 kolejno. Ponieważ nie ma dokąd iść z wierzchołka-7, wepchnij go do stosu. DFS na wykresie
Przejdź do poprzedniego wierzchołka (wierzchołek-6) i odwiedź jego wierzchołki potomne. Ale wszystkie jego wierzchołki potomne są odwiedzane, więc wsuń je do stosu. Układanie
Podobnie tworzony jest ostateczny stos. Ostateczny stos
Odwróć oryginalny wykres. DFS na odwróconym wykresie
Przeszukuj najpierw w głąb odwróconego wykresu.
Zacznij od górnego wierzchołka stosu. Przejdź przez wszystkie jego wierzchołki potomne. Po osiągnięciu już odwiedzonego wierzchołka powstaje jeden silnie połączony komponent.
Na przykład: Zdejmij wierzchołek-0 ze stosu. Zaczynając od wierzchołka-0, przechodź przez jego wierzchołki potomne (kolejno wierzchołek-0, wierzchołek-1, wierzchołek-2, wierzchołek-3) i oznacz je jako odwiedzone. Dziecko wierzchołka-3 jest już odwiedzone, więc te odwiedzone wierzchołki tworzą jeden silnie powiązany komponent. Zacznij od góry i
przejdź przez wszystkie wierzchołki. Podejdź do stosu i przebij górny wierzchołek, jeśli był już odwiedzony. W przeciwnym razie wybierz górny wierzchołek ze stosu i przejdź przez jego wierzchołki potomne, jak pokazano powyżej. Pop górny wierzchołek, jeśli został już odwiedzony Mocno połączony komponent
Zatem silnie połączonymi komponentami są: Wszystkie silnie połączone komponenty

Przykłady w Pythonie, Javie, 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(); )