Componente puternic conectate

Cuprins

Algoritmul lui Kosaraju
Exemple Python, Java, C ++
Complexitatea algoritmului lui Kosaraju
Aplicații pentru componente puternic conectate

În acest tutorial, veți afla cât de puternic sunt formate componentele conectate. De asemenea, veți găsi exemple de lucru ale algoritmului kosararju în C, C ++, Java și Python.

O componentă puternic conectată este porțiunea unui grafic direcționat în care există o cale de la fiecare vârf la alt vârf. Se aplică numai pe un grafic direcționat .

De exemplu:

Să luăm graficul de mai jos.

Grafic inițial

Componentele puternic conectate ale graficului de mai sus sunt:

Componente puternic conectate

Puteți observa că în prima componentă puternic conectată, fiecare vârf poate ajunge la celălalt vârf prin calea direcționată.

Aceste componente pot fi găsite folosind algoritmul lui Kosaraju .

Algoritmul lui Kosaraju

Algoritmul lui Kosaraju se bazează pe algoritmul de căutare adâncime-primul implementat de două ori.

Sunt implicați trei pași.

Efectuați o primă căutare în profunzime pe întregul grafic.
Să începem de la vertex-0, să vizităm toate vârfurile copilului său și să marcăm vârfurile vizitate ca terminate. Dacă un vârf duce la un vârf deja vizitat, atunci împingeți acest vârf în stivă.
De exemplu: Plecând de la vertex-0, mergeți la vertex-1, vertex-2 și apoi la vertex-3. Vertex-3 duce la vertex-0 deja vizitat, așa că împingeți vârful sursă (adică vertex-3) în stivă. DFS pe grafic
Mergeți la vârful anterior (vertex-2) și vizitați vârfurile copilului său, adică vertex-4, vertex-5, vertex-6 și vertex-7 secvențial. Deoarece nu există nicăieri de unde să mergem de la vertex-7, împingeți-l în stivă. DFS pe grafic
Mergeți la vârful anterior (vârf-6) și vizitați vârfurile copilului său. Dar, toate vârfurile copilului său sunt vizitate, așa că împingeți-le în teanc. Stivuire
În mod similar, se creează o stivă finală. Stiva finală
Inversați graficul original. DFS pe grafic inversat
Efectuați o căutare în profunzime pe graficul inversat.
Începeți de la vârful de sus al stivei. Parcurgeți toate vârfurile copilului său. Odată atins vârful deja vizitat, se formează o componentă puternic conectată.
De exemplu: scoateți vertex-0 din stivă. Începând de la vertex-0, parcurgeți vârfurile copilului său (vertex-0, vertex-1, vertex-2, vertex-3 în succesiune) și marcați-le ca vizitate. Copilul vertex-3 este deja vizitat, astfel încât aceste vârfuri vizitate formează o componentă puternic conectată. Începeți de sus și parcurgeți toate vârfurile.
Mergeți la stivă și deschideți vârful de sus dacă ați fost deja vizitat. În caz contrar, alegeți vârful de sus din stivă și traversați vârfurile copilului său, așa cum este prezentat mai sus. Apăsați vârful de sus dacă ați vizitat deja Componentă puternic conectată
Astfel, componentele puternic conectate sunt: Toate componentele puternic conectate

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