Močno povezane komponente

Kazalo

Kosarajujev algoritem
Primeri Python, Java, C ++
Kosarajujeva kompleksnost algoritma
Močno povezane komponente

V tej vadnici boste izvedeli, kako so oblikovane močno povezane komponente. Prav tako boste našli delovne primere algoritma kosararju v jezikih C, C ++, Java in Python.

Močno povezana komponenta je del usmerjenega grafa, v katerem je pot od vsake točke do druge točke. Velja samo za usmerjeni graf .

Na primer:

Vzemimo spodnji graf.

Začetni graf

Močno povezane komponente zgornjega grafa so:

Močno povezane komponente

Opazite lahko, da lahko v prvi močno povezani komponenti vsaka točka doseže drugo točko po usmerjeni poti.

Te komponente lahko najdemo s pomočjo algoritma Kosaraju .

Kosarajujev algoritem

Kosarajujev algoritem temelji na algoritmu iskanja globine prvi, ki je bil dvakrat implementiran.

Vključeni so trije koraki.

Najprej poiščite globino na celotnem grafu.
Začnimo od točke-0, obiščimo vse njene podrejene točke in obiskano točko označimo kot končano. Če oglišče vodi v že obiskano oglišče, ga potisnite v sklad.
Na primer: Začnite od točke-0, pojdite do točke-1, točke-2 in nato do točke-3. Vertex-3 vodi do že obiskane vertex-0, zato potisnite izvorno točko (tj. Vertex-3) v sklad. DFS na grafu
Pojdite na prejšnjo točko (vertex-2) in zaporedoma obiščite njene podrejene točke, tj. Vertex-4, vertex-5, vertex-6 in vertex-7. Ker od točke 7 ni kam iti, jo potisnite v sklad. DFS na grafu
Pojdite na prejšnjo točko (vertex-6) in obiščite njene podrejene točke. Vendar so obiskane vse njene podrejene točke, zato jih potisnite v sklad. Zlaganje
Podobno se ustvari končni sklad. Končni kup
Obrni prvotni graf. DFS na obrnjenem grafu
Izvedite iskanje po globini na obrnjenem grafu.
Začnite od zgornje točke svežnja. Prehodite se skozi vse njene podrejene točke. Ko dosežemo že obiskano oglišče, nastane ena močno povezana komponenta.
Na primer: Pop vertex-0 iz sklada. Začenši z oglišča-0, se premikajte po njegovih podrejenih ogliščih (oglišče-0, oglišče-1, ohišje-2, oglišče-3) in jih označite kot obiskana. Podreje točke 3 je že obiskano, zato ta obiskana oglišča tvorijo eno močno povezano komponento. Začnite z vrha in se pomaknite skozi vse oglišča.
Pojdite na sklad in odprite zgornjo točko, če ste že obiskali. V nasprotnem primeru izberite zgornjo točko iz sklada in se pomaknite skozi njene podrejene točke, kot je prikazano zgoraj. Če je že obiskano, odprite zgornjo točko Močno povezana komponenta
Tako so močno povezane komponente: Vse močno povezane komponente

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