Čvrsto povezane komponente

Sadržaj

Kosarajuov algoritam
Primjeri Python, Java, C ++
Složenost algoritma Kosarajua
Čvrsto povezane komponente

U ovom vodiču naučit ćete kako se formiraju čvrsto povezane komponente. Također ćete naći radne primjere kosararjuovog algoritma na C, C ++, Java i Python.

Snažno povezana komponenta je dio usmjerenog grafa u kojem postoji put od svakog vrha do drugog vrha. Primjenjivo je samo na usmjereni graf .

Na primjer:

Uzmimo grafikon u nastavku.

Početni graf

Snažno povezane komponente gornjeg grafa su:

Čvrsto povezane komponente

Možete primijetiti da u prvoj jako povezanoj komponenti svaki vrh može doći do drugog vrha usmjerenim putem.

Te se komponente mogu pronaći pomoću Kosarajuevog algoritma .

Kosarajuov algoritam

Kosarajuov algoritam temelji se na algoritmu pretraživanja dubine prvi puta implementiranom dva puta.

Uključena su tri koraka.

Izvršite prvo dubinsko pretraživanje na cijelom grafikonu.
Krenimo od vrha-0, posjetimo sve njegove podređene vrhove i označimo posjećene vrhove kao gotove. Ako vrh vodi do već posjećenog vrha, gurnite ga u stog.
Na primjer: Polazeći od vrha-0, idite na vrh-1, vrh-2, a zatim u vrh-3. Vrh 3 vodi do već posjećenog vrha 0, pa gurnite izvorni vrh (tj. Vrh 3) u hrpu. DFS na grafikonu
Idite na prethodni vrh (vrh-2) i uzastopno posjetite njegove podređene vrhove, tj. Vrh-4, vrh-5, vrh-6 i vrh-7. Budući da se od vrha-7 nema kamo, gurnite ga u hrpu. DFS na grafikonu
Idite na prethodni vrh (vrh-6) i posjetite njegove podređene vrhove. Ali, posjećuju se svi njegovi podređeni vrhovi, pa ih gurnite u hrpu. Slaganje
Slično tome, stvara se završni stog. Konačni stog
Obrni izvorni grafikon. DFS na obrnutom grafikonu
Izvršite pretraživanje prvo po dubini na obrnutom grafikonu.
Počnite od gornjeg vrha hrpe. Krenite kroz sve njegove donje dijelove. Kad se dosegne već posjećeni vrh, formira se jedna čvrsto povezana komponenta.
Na primjer: Pop vertex-0 iz hrpe. Polazeći od vrha-0, pređite kroz njegove podređene vrhove (vrh-0, vrh-1, vrh-2, vrh-3 u nizu) i označite ih kao posjećene. Dijete vrha-3 je već posjećeno, tako da ti posjećeni vrhovi čine jednu čvrsto povezanu komponentu. Krenite od vrha i krenite kroz sve vrhove
Idite na hrpu i popnite gornji vrh ako ste ga već posjetili. Inače, odaberite gornji vrh iz snopa i pređite kroz njegove podređene vrhove kao što je gore prikazano. Otvorite gornji vrh ako ste ga već posjetili Čvrsto povezana komponenta
Dakle, čvrsto povezane komponente su: Sve čvrsto povezane komponente

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