Tvirtai prijungti komponentai

Turinys

„Kosaraju“ algoritmas
„Python“, „Java“, „C ++“ pavyzdžiai
„Kosaraju“ algoritmų sudėtingumas
Stipriai sujungtos komponentų programos

Šioje pamokoje sužinosite, kaip stipriai sujungti komponentai. Taip pat rasite veikiančių kosararju algoritmo pavyzdžių C, C ++, Java ir Python.

Tvirtai sujungtas komponentas yra nukreipto grafiko dalis, kurioje yra kelias iš kiekvienos viršūnės į kitą. Jis taikomas tik nukreiptame grafike .

Pavyzdžiui:

Paimkime žemiau pateiktą grafiką.

Pradinis grafikas

Tvirtai susiję aukščiau pateikto grafiko komponentai yra šie:

Tvirtai sujungti komponentai

Galite pastebėti, kad pirmajame stipriai sujungtame komponente kiekviena viršūnė gali pasiekti kitą viršūnę nukreiptu keliu.

Šiuos komponentus galima rasti naudojant Kosaraju algoritmą .

„Kosaraju“ algoritmas

„Kosaraju“ algoritmas yra pagrįstas du kartus įgyvendinto paieškos gylio algoritmu.

Tai susiję su trim žingsniais.

Pirmiausia atlikite gylio paiešką visame grafike.
Pradėkime nuo viršūnės-0, aplankykime visas jos antrines viršūnes ir pažymime aplankytas viršūnes kaip atliktas. Jei viršūnė veda į jau aplankytą viršūnę, stumkite šią viršūnę į kaminą.
Pvz .: Pradėdami nuo viršūnės-0, eikite į viršūnę-1, viršūnę-2 ir tada į viršūnę-3. Viršūnė-3 veda prie jau aplankytos viršūnės-0, todėl įstumkite šaltinio viršūnę (t. Y. Viršūnę-3) į kaminą. DFS diagramoje
Eikite į ankstesnę viršūnę (2-ą viršūnę) ir aplankykite jos antrines viršūnes, ty 4-ą, 5-ą, 6-ą ir 6-ą. Kadangi nuo viršūnės-7 nėra kur eiti, stumkite jį į kaminą. DFS grafike
Eikite į ankstesnę viršūnę (viršūnę-6) ir aplankykite jos antrines viršūnes. Bet visos jo antrinės viršūnės yra aplankytos, todėl stumkite ją į kaminą. Stacking
Panašiai sukuriamas galutinis kaminas. Galutinis krūva
Apverskite pradinį grafiką. DFS atvirkštiniame grafike
Pirmiausia atlikite gylio paiešką atvirkštiniame grafike.
Pradėkite nuo viršutinės kamino viršūnės. Važiuokite per visas savo vaiko viršūnes. Pasiekus jau aplankytą viršūnę, susidaro vienas stipriai susijęs komponentas.
Pvz .: Iškelkite viršūnę-0 iš kamino. Pradėdami nuo viršūnės-0, eikite per savo vaiko viršūnes (viršūnė-0, viršūnė-1, viršūnė-2, viršūnė-3 iš eilės) ir pažymėkite jas kaip aplankytas. 3 viršūnės vaikas jau lankomas, todėl šios aplankytos viršūnės sudaro vieną stipriai susijungusį komponentą. Pradėkite nuo viršaus ir
pereikite per visas viršūnes. Eikite į kaminą ir iššokite viršutinę viršūnę, jei jau lankėtės. Kitu atveju iš kamino pasirinkite viršutinę viršūnę ir eikite per jos antrines viršūnes, kaip nurodyta aukščiau. Pasirodykite viršutinė viršūnė, jei jau lankėtės Tvirtai sujungtas komponentas
Taigi stipriai sujungti komponentai yra šie: Visi stipriai sujungti komponentai

„Python“, „Java“, „C ++“ pavyzdžiai

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