Stærkt forbundne komponenter

Indholdsfortegnelse

Kosarajus algoritme
Python, Java, C ++ eksempler
Kosarajus algoritmekompleksitet
Komponenter med stærkt forbundne komponenter

I denne vejledning lærer du, hvor stærkt tilsluttede komponenter er dannet. Du finder også arbejdseksempler på kosararjus algoritme i C, C ++, Java og Python.

En stærkt forbundet komponent er den del af en rettet graf, hvor der er en sti fra hvert toppunkt til et andet toppunkt. Det gælder kun på en rettet graf .

For eksempel:

Lad os tage grafen nedenfor.

Indledende graf

De stærkt forbundne komponenter i ovenstående graf er:

Stærkt tilsluttede komponenter

Du kan se, at i den første stærkt forbundne komponent kan hvert toppunkt nå det andet toppunkt gennem den rettet vej.

Disse komponenter kan findes ved hjælp af Kosarajus algoritme .

Kosarajus algoritme

Kosaraju's algoritme er baseret på den dybde-første søgealgoritme implementeret to gange.

Tre trin er involveret.

Udfør en dybde første søgning på hele grafen.
Lad os starte fra toppunkt-0, besøge alle dets underordnede hjørner og markere de besøgte hjørner som færdige. Hvis et toppunkt fører til et allerede besøgt toppunkt, skal du skubbe dette toppunkt til stakken.
For eksempel: Start fra toppunkt-0, gå til toppunkt-1, toppunkt-2 og derefter til toppunkt-3. Vertex-3 fører til allerede besøgt toppunkt-0, så skub kildepunktet (dvs. toppunkt-3) ind i stakken. DFS på grafen
Gå til det forrige toppunkt (vertex-2) og besøg dets underordnede hjørner, dvs. vertex-4, vertex-5, vertex-6 og vertex-7 i rækkefølge. Da der ikke er nogen steder at gå fra vertex-7, skal du skubbe den ind i stakken. DFS på grafen
Gå til det forrige toppunkt (vertex-6) og besøg dets underordnede hjørner. Men alle dets underordnede hjørner er besøgt, så skub det ind i stakken. Stacking
Tilsvarende oprettes en endelig stack. Endelig stak
Vend den originale graf. DFS på omvendt graf
Udfør dybde-første søgning på den omvendte graf.
Start fra toppen af stakken. Kør gennem alle sine børnehjørner. Når det allerede besøgte toppunkt er nået, dannes en stærkt forbundet komponent.
For eksempel: Pop vertex-0 fra stakken. Startende fra toppunkt-0, kryds gennem dets underordnede hjørner (vertex-0, vertex-1, vertex-2, vertex-3 i rækkefølge) og markér dem som besøgt. Barnet til vertex-3 er allerede besøgt, så disse besøgte hjørner udgør en stærkt forbundet komponent. Start fra toppen og krydse gennem alle hjørnerne
Gå til stakken og pop øverste hjørne, hvis den allerede er besøgt. Ellers skal du vælge det øverste toppunkt fra stakken og krydse gennem dets underordnede hjørner som præsenteret ovenfor. Pop det øverste toppunkt, hvis det allerede er besøgt Stærkt tilsluttet komponent
Således er de stærkt tilsluttede komponenter: Alle stærkt tilsluttede komponenter

Python, Java, C ++ eksempler

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