Spēcīgi savienoti komponenti

Satura rādītājs

Kosaraju algoritms
Python, Java, C ++ piemēri
Kosaraju algoritmu sarežģītība
Cieši saistītas komponentu lietojumprogrammas

Šajā apmācībā jūs uzzināsiet, cik spēcīgi savienoti komponenti tiek veidoti. Jūs atradīsit arī piemērotus kosararju algoritma piemērus C, C ++, Java un Python.

Cieši saistīta sastāvdaļa ir virzītā grafa daļa, kurā ir ceļš no katras virsotnes uz citu virsotni. Tas ir piemērojams tikai virzītam grafikam .

Piemēram:

Ņemsim zemāk redzamo diagrammu.

Sākotnējais grafiks

Iepriekš diagrammas cieši saistītās sastāvdaļas ir:

Cieši savienoti komponenti

Jūs varat novērot, ka pirmajā stingri savienotajā komponentā katra virsotne var sasniegt otru virsotni pa virzīto ceļu.

Šos komponentus var atrast, izmantojot Kosaraju algoritmu .

Kosaraju algoritms

Kosaraju algoritms ir balstīts uz divreiz ieviesto dziļuma meklēšanas algoritmu.

Ir iesaistīti trīs soļi.

Visā diagrammā vispirms veiciet dziļuma meklēšanu.
Sāksim no virsotnes-0, apmeklēsim visas tās pakārtotās virsotnes un atzīmēsim apmeklētās virsotnes kā pabeigtas. Ja virsotne ved uz jau apmeklētu virsotni, nospiediet šo virsotni pie kaudzes.
Piemēram: Sākot no virsotnes-0, dodieties uz virsotni-1, virsotni-2 un pēc tam uz virsotni-3. Virsotne-3 ved uz jau apmeklēto virsotni-0, tāpēc stumiet avota virsotni (ti, virsotni-3) kaudzē. DFS diagrammā
Pārejiet uz iepriekšējo virsotni (2. virsotne) un secīgi apmeklējiet tās virsotnes, ti, 4., 5., 6. un 7. virsotni. Tā kā no 7. virsotnes nav kur iet, iespiediet to kaudzē. DFS uz diagrammas
Pārejiet uz iepriekšējo virsotni (virsotne-6) un apmeklējiet tās bērnu virsotnes. Bet tiek apmeklētas visas tā apakšējās virsotnes, tāpēc iespiediet to kaudzē. Stacking
Tāpat tiek izveidots pēdējais kaudze. Galīgā kaudze
Apgrieziet sākotnējo diagrammu. DFS apgrieztā grafikā
Veiciet dziļuma meklēšanu apgrieztajā grafikā.
Sāciet no kaudzes augšējās virsotnes. Pārvietojieties pa visām tā apakšējām virsotnēm. Kad ir sasniegta jau apmeklētā virsotne, veidojas viena cieši saistīta sastāvdaļa.
Piemēram: Pop virsotne-0 no kaudzes. Sākot no virsotnes-0, šķērsojiet tās bērna virsotnes (virsotne-0, virsotne-1, virsotne-2, virsotne-3 pēc kārtas) un atzīmējiet tās kā apmeklētas. 3. virsotnes bērns jau ir apmeklēts, tāpēc šīs apmeklētās virsotnes veido vienu stipri savienotu komponentu. Sāciet no augšas un šķērsojiet visas virsotnes.
Pārejiet uz kaudzīti un uzlieciet augšējo virsotni, ja tā jau ir apmeklēta. Pretējā gadījumā no kaudzes izvēlieties augšējo virsotni un pārvietojieties pa tās bērnu virsotnēm, kā parādīts iepriekš. Pop augšējā virsotne, ja tas jau ir apmeklēts Spēcīgi savienots komponents
Tādējādi stingri savienotie komponenti ir: Visi stingri savienotie komponenti

Python, Java, C ++ piemēri

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