Komponen yang Sangat Bersambung

Isi kandungan

Algoritma Kosaraju
Contoh Python, Java, C ++
Kerumitan Algoritma Kosaraju
Aplikasi Komponen yang Sangat Berkaitan

Dalam tutorial ini, anda akan mengetahui bagaimana komponen yang bersambung kuat terbentuk. Anda juga akan mendapat contoh algoritma kosararju yang berfungsi di C, C ++, Java dan Python.

Komponen yang bersambung kuat adalah bahagian graf yang diarahkan di mana terdapat jalan dari setiap bucu ke bucu yang lain. Ia hanya berlaku pada grafik yang diarahkan .

Sebagai contoh:

Mari kita ambil grafik di bawah.

Graf awal

Komponen grafik yang berkaitan dengan kuat adalah:

Komponen yang sangat bersambung

Anda dapat memerhatikan bahawa pada komponen pertama yang sangat terhubung, setiap bucu dapat mencapai bucu lain melalui jalan yang diarahkan.

Komponen ini boleh didapati menggunakan Algoritma Kosaraju .

Algoritma Kosaraju

Algoritma Kosaraju didasarkan pada algoritma carian mendalam pertama yang dilaksanakan dua kali.

Tiga langkah terlibat.

Lakukan carian pertama yang mendalam pada keseluruhan graf.
Mari kita mulakan dari bucu-0, kunjungi semua simpul anak-anaknya, dan tandakan bucu yang dikunjungi sebagai selesai. Sekiranya bucu mengarah ke bucu yang sudah dikunjungi, maka tolak bucu ini ke tumpukan.
Contohnya: Bermula dari bucu-0, pergi ke bucu-1, bucu-2, dan kemudian ke bucu-3. Vertex-3 mengarah ke vertex-0 yang sudah dikunjungi, jadi tolak vertex sumber (iaitu. Vertex-3) ke dalam stack. DFS pada grafik
Pergi ke bucu sebelumnya (vertex-2) dan lawati bucu anak-anaknya iaitu vertex-4, vertex-5, vertex-6 dan vertex-7 secara berturutan. Oleh kerana tidak ada jalan keluar dari bucu-7, dorong ke dalam timbunan. DFS pada graf
Pergi ke bucu sebelumnya (bucu-6) dan lawati bucu anak-anaknya. Tetapi, semua simpul anak-anaknya dikunjungi, jadi tolak ke dalam timbunan. Menyusun
Begitu juga, timbunan akhir dibuat. Tumpuan Akhir
Balikkan graf asal. DFS pada graf terbalik
Lakukan carian pertama-mendalam pada graf terbalik.
Mulakan dari puncak atas timbunan. Melintasi semua bucu anaknya. Setelah titik yang telah dikunjungi tercapai, satu komponen yang tersambung kuat akan terbentuk.
Contohnya: Pop vertex-0 dari timbunan. Bermula dari bucu-0, melintasi bucu anak-anaknya (bucu-0, bucu-1, bucu-2, bucu-3 secara berurutan) dan tandakan sebagai dilawati. Anak simpul-3 sudah dikunjungi, jadi bucu yang dikunjungi ini membentuk satu komponen yang sangat berkaitan. Mula dari atas dan melintasi semua bucu
Pergi ke tumpukan dan letakkan bucu atas jika sudah dikunjungi. Jika tidak, pilih bucu atas dari timbunan dan melintasi bucu anak-anaknya seperti yang ditunjukkan di atas. Muncul bucu atas jika sudah dikunjungi Komponen yang sangat bersambung
Oleh itu, komponen yang bersambung kuat adalah: Semua komponen yang bersambung kuat

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