Komponen yang Sangat Terhubung

Daftar Isi

Algoritma Kosaraju
Contoh Python, Java, C ++
Kompleksitas Algoritma Kosaraju
Aplikasi Komponen yang Sangat Terhubung

Dalam tutorial ini, Anda akan mempelajari bagaimana komponen yang sangat terhubung terbentuk. Juga, Anda akan menemukan contoh kerja algoritma kosarju di C, C ++, Java dan Python.

Komponen yang sangat terhubung adalah bagian dari graf berarah yang di dalamnya terdapat jalur dari setiap simpul ke simpul lain. Ini hanya berlaku pada grafik berarah .

Sebagai contoh:

Mari kita ambil grafik di bawah ini.

Grafik awal

Komponen yang sangat terhubung dari grafik di atas adalah:

Komponen yang sangat terhubung

Anda dapat mengamati bahwa pada komponen terkoneksi kuat pertama, setiap simpul dapat mencapai simpul lainnya melalui jalur terarah.

Komponen ini dapat ditemukan menggunakan Algoritma Kosaraju .

Algoritma Kosaraju

Algoritma Kosaraju didasarkan pada algoritma pencarian depth-first yang diimplementasikan dua kali.

Ada tiga langkah yang terlibat.

Lakukan penelusuran pertama yang mendalam di seluruh grafik.
Mari kita mulai dari simpul-0, kunjungi semua simpul anak, dan tandai simpul yang dikunjungi sebagai selesai. Jika simpul mengarah ke simpul yang sudah dikunjungi, kemudian dorong simpul ini ke tumpukan.
Contoh: Mulai dari simpul-0, lanjutkan ke simpul-1, simpul-2, lalu ke simpul-3. Simpul-3 mengarah ke simpul-0 yang sudah dikunjungi, jadi dorong simpul sumber (mis. Simpul-3) ke dalam tumpukan. DFS pada graf
Pergi ke simpul sebelumnya (simpul-2) dan kunjungi simpul anaknya yaitu simpul-4, simpul-5, simpul-6 dan simpul-7 secara berurutan. Karena tidak ada tempat untuk pergi dari vertex-7, dorong ke dalam tumpukan. DFS pada grafik
Pergi ke simpul sebelumnya (simpul-6) dan kunjungi simpul anaknya. Tapi, semua simpul turunannya dikunjungi, jadi dorong ke dalam tumpukan. Stacking
Demikian pula, tumpukan akhir dibuat. Tumpukan Terakhir
Balikkan grafik aslinya. DFS pada grafik terbalik
Lakukan penelusuran pertama kedalaman pada grafik terbalik.
Mulai dari puncak atas tumpukan. Lintasi semua simpul turunannya. Setelah simpul yang sudah dikunjungi tercapai, satu komponen yang terhubung kuat terbentuk.
Misalnya: Pop vertex-0 dari tumpukan. Mulai dari simpul-0, lintasi simpul anaknya (simpul-0, simpul-1, simpul-2, simpul-3 berurutan) dan tandai sebagai telah dikunjungi. Anak dari simpul-3 sudah dikunjungi, jadi simpul yang dikunjungi ini membentuk satu komponen yang terhubung kuat. Mulai dari atas dan lintasi semua simpul
Pergi ke tumpukan dan letuskan simpul atas jika sudah dikunjungi. Jika tidak, pilih puncak atas dari tumpukan dan lintasi simpul anak seperti yang disajikan di atas. Pop puncak atas jika sudah dikunjungi Komponen yang sangat terhubung
Jadi, komponen yang terhubung kuat adalah: Semua komponen yang terhubung 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(); )