Sterkt tilkoblede komponenter

Innholdsfortegnelse

Kosarajus algoritme
Python, Java, C ++ eksempler
Kosarajus algoritmekompleksitet
Sterkt tilkoblede komponenter

I denne opplæringen lærer du hvor sterkt tilkoblede komponenter dannes. Du vil også finne eksempler på kosararjus algoritme i C, C ++, Java og Python.

En sterkt koblet komponent er den delen av en rettet graf der det er en bane fra hvert toppunkt til et annet toppunkt. Det gjelder bare på en rettet graf .

For eksempel:

La oss ta grafen nedenfor.

Innledende graf

De sterkt koblede komponentene i grafen ovenfor er:

Sterkt tilkoblede komponenter

Du kan se at i den første sterkt tilkoblede komponenten kan hvert toppunkt nå det andre toppunktet gjennom den rettet vei.

Disse komponentene kan bli funnet ved hjelp av Kosarajus algoritme .

Kosarajus algoritme

Kosarajus algoritme er basert på dybden-første søkealgoritmen implementert to ganger.

Tre trinn er involvert.

Utfør et første dybdesøk på hele grafen.
La oss starte fra toppunkt-0, besøke alle barnets hjørner og merke de besøkte hjørnene som ferdig. Hvis et toppunkt fører til et allerede besøkt toppunkt, skyver du dette toppunktet til stabelen.
For eksempel: Fra toppunkt-0, gå til toppunkt-1, toppunkt-2 og deretter til toppunkt-3. Vertex-3 fører til allerede besøkt toppunkt-0, så skyv kildepunktet (dvs. toppunkt-3) inn i stabelen. DFS på grafen
Gå til forrige toppunkt (toppunkt-2) og besøk barnets toppunkt, dvs. toppunkt-4, toppunkt-5, toppunkt-6 og toppunkt-7 sekvensielt. Siden det ikke er noe å gå fra toppunkt 7, skyver du det inn i bunken. DFS på grafen
Gå til forrige toppunkt (toppunkt-6) og besøk barnets toppunkt. Men alle barnets hjørner blir besøkt, så skyv den inn i bunken. Stacking
Tilsvarende opprettes en endelig stack. Endelig stabel
Snu originalgrafen. DFS på omvendt graf
Utfør første dybdesøk på den omvendte grafen.
Start fra toppen av bunken. Kryss gjennom alle barnets hjørner. Når det allerede besøkte toppunktet er nådd, dannes en sterkt koblet komponent.
For eksempel: Pop toppunkt-0 fra stabelen. Starter fra toppunkt-0, kryss gjennom barnets toppunkt (toppunkt-0, toppunkt-1, toppunkt-2, toppunkt-3 i rekkefølge) og merk dem som besøkt. Barnet til toppunkt-3 er allerede besøkt, så disse besøkte toppunktene danner en sterkt koblet komponent. Start fra toppen og krysse gjennom alle toppunktene
Gå til stabelen og sprett toppunktet hvis du allerede har besøkt det. Ellers velger du toppunktet fra bunken og krysser gjennom underordnede hjørner som presentert ovenfor. Popp toppunktet hvis det allerede er besøkt Sterkt tilkoblet komponent
Dermed er de sterkt tilkoblede komponentene: Alle sterkt tilkoblede komponenter

Python, Java, C ++ eksempler

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