Güçlü Bağlantılı Bileşenler

İçindekiler

Kosaraju Algoritması
Python, Java, C ++ örnekleri
Kosaraju'nun Algoritma Karmaşıklığı
Güçlü Bağlantılı Bileşen Uygulamaları

Bu eğitimde, bileşenlerin ne kadar güçlü bir şekilde oluşturulduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da kosararju algoritmasının çalışan örneklerini bulacaksınız.

Güçlü bir şekilde bağlı bir bileşen, yönlendirilmiş bir grafiğin, her bir tepe noktasından başka bir tepe noktasına bir yolun olduğu bölümüdür. Yalnızca yönlendirilmiş bir grafiğe uygulanabilir .

Örneğin:

Aşağıdaki grafiği alalım.

İlk grafik

Yukarıdaki grafiğin güçlü bir şekilde bağlantılı bileşenleri şunlardır:

Güçlü bağlantılı bileşenler

İlk güçlü şekilde bağlanmış bileşende, her köşenin, yönlendirilen yol üzerinden diğer tepe noktasına ulaşabildiğini gözlemleyebilirsiniz.

Bu bileşenler, Kosaraju Algoritması kullanılarak bulunabilir .

Kosaraju Algoritması

Kosaraju'nun Algoritması, iki kez uygulanan önce derinlik arama algoritmasına dayanmaktadır.

Üç adım söz konusudur.

Tüm grafik üzerinde ilk derinlik araması yapın.
Köşe-0'dan başlayalım, tüm alt köşelerini ziyaret edelim ve ziyaret edilen köşeleri tamam olarak işaretleyelim. Bir köşe zaten ziyaret edilmiş bir köşeye götürürse, bu köşeyi yığına itin.
Örneğin: Köşe-0'dan başlayarak, köşe-1, köşe-2 ve sonra köşe-3'e gidin. Köşe-3 daha önce ziyaret edilen köşe-0'a götürür, bu nedenle kaynak tepe noktasını (yani köşe-3) yığına itin. Grafikteki DFS Bir
önceki tepe noktasına (köşe-2) gidin ve alt köşelerini, yani sırasıyla köşe-4, köşe-5, köşe-6 ve köşe-7'yi ziyaret edin. Vertex-7'den gidecek hiçbir yer olmadığından, onu yığının içine itin. Grafikte DFS
Önceki tepe noktasına (köşe-6) gidin ve alt köşelerini ziyaret edin. Ancak, tüm alt köşeleri ziyaret edildi, bu yüzden onu yığının içine itin. Yığınlama
Benzer şekilde, son bir yığın oluşturulur. Nihai Yığın
Orijinal grafiği ters çevirin. Ters grafikte DFS
Ters çevrilmiş grafikte önce derinlik araması yapın.
Yığının en üst köşesinden başlayın. Tüm alt köşelerinden geçin. Zaten ziyaret edilen tepe noktasına ulaşıldığında, güçlü bir şekilde bağlanmış bir bileşen oluşturulur.
Örneğin: Yığından köşe-0'ı açın. Köşe-0'dan başlayarak, alt köşelerinden (sırayla köşe-0, köşe-1, köşe-2, köşe-3) geçin ve bunları ziyaret edilmiş olarak işaretleyin. Köşe-3 alt öğesi zaten ziyaret edildi, bu nedenle ziyaret edilen bu köşeler güçlü bir şekilde bağlantılı bir bileşen oluşturur. En üstten başlayın ve tüm köşelerden
geçin Yığına gidin ve zaten ziyaret edilmişse üst tepe noktasını açın. Aksi takdirde, yığından en üst köşeyi seçin ve yukarıda gösterildiği gibi alt köşelerinden geçin. Zaten ziyaret edildiyse üst köşeyi açın Güçlü bir şekilde bağlı bileşen
Bu nedenle, güçlü bir şekilde bağlı bileşenler şunlardır: Tüm güçlü bağlantılı bileşenler

Python, Java, C ++ örnekleri

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