Stark verbundene Komponenten

Inhaltsverzeichnis

Kosarajus Algorithmus
Beispiele für Python, Java, C ++
Kosarajus Algorithmuskomplexität
Stark verbundene Komponentenanwendungen

In diesem Tutorial erfahren Sie, wie stark verbundene Komponenten gebildet werden. Außerdem finden Sie Arbeitsbeispiele für den Kosararju-Algorithmus in C, C ++, Java und Python.

Eine stark verbundene Komponente ist der Teil eines gerichteten Graphen, in dem sich ein Pfad von jedem Scheitelpunkt zu einem anderen Scheitelpunkt befindet. Es ist nur auf einen gerichteten Graphen anwendbar .

Beispielsweise:

Nehmen wir die folgende Grafik.

Anfangsgrafik

Die stark verbundenen Komponenten des obigen Diagramms sind:

Stark verbundene Komponenten

Sie können beobachten, dass in der ersten stark verbundenen Komponente jeder Scheitelpunkt den anderen Scheitelpunkt über den gerichteten Pfad erreichen kann.

Diese Komponenten können mithilfe des Kosaraju-Algorithmus gefunden werden .

Kosarajus Algorithmus

Der Kosaraju-Algorithmus basiert auf dem zweimal implementierten Tiefensuchalgorithmus.

Es sind drei Schritte erforderlich.

Führen Sie eine Tiefensuche für das gesamte Diagramm durch.
Beginnen wir mit Scheitelpunkt 0, besuchen alle untergeordneten Scheitelpunkte und markieren die besuchten Scheitelpunkte als erledigt. Wenn ein Scheitelpunkt zu einem bereits besuchten Scheitelpunkt führt, verschieben Sie diesen Scheitelpunkt auf den Stapel.
Beispiel: Gehen Sie von Scheitelpunkt 0 aus zu Scheitelpunkt 1, Scheitelpunkt 2 und dann zu Scheitelpunkt 3. Scheitelpunkt-3 führt zu bereits besuchtem Scheitelpunkt-0, also schieben Sie den Quellscheitelpunkt (dh Scheitelpunkt-3) in den Stapel. DFS im Diagramm
Gehen Sie zum vorherigen Scheitelpunkt (Scheitelpunkt-2) und besuchen Sie die untergeordneten Scheitelpunkte, dh Scheitelpunkt-4, Scheitelpunkt-5, Scheitelpunkt-6 und Scheitelpunkt-7, nacheinander. Da Vertex-7 nirgendwo zu finden ist, schieben Sie es in den Stapel. DFS in der Grafik
Gehen Sie zum vorherigen Scheitelpunkt (Scheitelpunkt-6) und besuchen Sie die untergeordneten Scheitelpunkte. Es werden jedoch alle untergeordneten Scheitelpunkte besucht. Schieben Sie sie daher in den Stapel. Stapeln
In ähnlicher Weise wird ein endgültiger Stapel erstellt. Final Stack
Kehren Sie das ursprüngliche Diagramm um. DFS auf umgekehrtem Diagramm
Führen Sie eine Tiefensuche im umgekehrten Diagramm durch.
Beginnen Sie am oberen Scheitelpunkt des Stapels. Durchqueren Sie alle untergeordneten Eckpunkte. Sobald der bereits besuchte Scheitelpunkt erreicht ist, wird eine stark verbundene Komponente gebildet.
Zum Beispiel: Pop vertex-0 vom Stapel. Beginnen Sie mit Scheitelpunkt 0 und durchlaufen Sie die untergeordneten Scheitelpunkte (Scheitelpunkt 0, Scheitelpunkt 1, Scheitelpunkt 2, Scheitelpunkt 3 nacheinander) und markieren Sie sie als besucht. Das Kind von Vertex-3 ist bereits besucht, daher bilden diese besuchten Vertices eine stark verbundene Komponente. Beginnen Sie von oben und durchlaufen Sie alle Scheitelpunkte.
Gehen Sie zum Stapel und öffnen Sie den oberen Scheitelpunkt, falls dieser bereits besucht wurde. Wählen Sie andernfalls den oberen Scheitelpunkt aus dem Stapel aus und durchlaufen Sie die untergeordneten Scheitelpunkte wie oben dargestellt. Pop den oberen Scheitelpunkt, wenn bereits besucht Stark verbundene Komponente
Somit sind die stark verbundenen Komponenten: Alle stark verbundenen Komponenten

Beispiele für 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(); )