Sterk verbonden componenten

Inhoudsopgave

Kosaraju's algoritme
Python, Java, C ++ voorbeelden
De complexiteit van het algoritme van Kosaraju
Sterk verbonden componenten toepassingen

In deze tutorial leer je hoe sterk verbonden componenten worden gevormd. Ook vindt u werkende voorbeelden van het algoritme van kosararju in C, C ++, Java en Python.

Een sterk verbonden component is het deel van een gerichte graaf waarin er een pad is van elk hoekpunt naar een ander hoekpunt. Het is alleen van toepassing op een gerichte grafiek .

Bijvoorbeeld:

Laten we de onderstaande grafiek nemen.

Eerste grafiek

De sterk verbonden componenten van bovenstaande grafiek zijn:

Sterk verbonden componenten

Je kunt zien dat in de eerste sterk verbonden component elk hoekpunt het andere hoekpunt kan bereiken via het gerichte pad.

Deze componenten kunnen worden gevonden met behulp van Kosaraju's algoritme .

Kosaraju's algoritme

Het algoritme van Kosaraju is gebaseerd op het diepte-eerst zoekalgoritme dat twee keer is geïmplementeerd.

Er zijn drie stappen bij betrokken.

Voer een dieptezoekopdracht uit op de hele grafiek.
Laten we beginnen met vertex-0, alle onderliggende hoekpunten bezoeken en de bezochte hoekpunten markeren als voltooid. Als een hoekpunt naar een reeds bezocht hoekpunt leidt, duw dit hoekpunt dan naar de stapel.
Bijvoorbeeld: ga vanaf hoekpunt-0 naar hoekpunt-1, hoekpunt-2 en vervolgens naar hoekpunt-3. Vertex-3 leidt naar reeds bezochte vertex-0, dus duw de bronvertex (dwz vertex-3) in de stapel. DFS op de grafiek
Ga naar het vorige hoekpunt (hoekpunt-2) en bezoek de onderliggende hoekpunten, dwz hoekpunt-4, hoekpunt-5, hoekpunt-6 en hoekpunt-7 opeenvolgend. Omdat je nergens heen kunt vanaf hoekpunt-7, duw je het in de stapel. DFS op de grafiek
Ga naar het vorige hoekpunt (hoekpunt-6) en bezoek de onderliggende hoekpunten. Maar alle onderliggende hoekpunten worden bezocht, dus duw het in de stapel. Stapelen
Op dezelfde manier wordt er een laatste stapel gemaakt. Laatste stapel
Keer de oorspronkelijke grafiek om. DFS op omgekeerde grafiek
Voer een diepte-eerste zoekopdracht uit op de omgekeerde grafiek.
Begin vanaf het bovenste hoekpunt van de stapel. Doorkruis al zijn onderliggende hoekpunten. Zodra de reeds bezochte top is bereikt, wordt één sterk verbonden component gevormd.
Bijvoorbeeld: Pop vertex-0 van de stapel. Ga vanaf hoekpunt-0 door de onderliggende hoekpunten (hoekpunt-0, hoekpunt-1, hoekpunt-2, hoekpunt-3 in volgorde) en markeer ze als bezocht. Het kind van vertex-3 is al bezocht, dus deze bezochte hoekpunten vormen één sterk verbonden component. Begin vanaf de bovenkant en doorloop alle hoekpunten.
Ga naar de stapel en laat het bovenste hoekpunt springen als het al bezocht is. Kies anders het bovenste hoekpunt van de stapel en doorloop de onderliggende hoekpunten zoals hierboven weergegeven. Pop het bovenste hoekpunt als het al bezocht is Sterk verbonden component
De sterk verbonden componenten zijn dus: Alle sterk verbonden componenten

Python, Java, C ++ voorbeelden

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