Starkt anslutna komponenter

Innehållsförteckning

Kosarajus algoritm
Python, Java, C ++ exempel
Kosarajus algoritmkomplexitet
Applikationer med starkt anslutna komponenter

I denna handledning lär du dig hur starkt anslutna komponenter bildas. Du hittar också arbetsexempel på kosararjus algoritm i C, C ++, Java och Python.

En starkt ansluten komponent är den del av en riktad graf där det finns en bana från varje toppunkt till en annan toppunkt. Det är endast tillämpligt på en riktad graf .

Till exempel:

Låt oss ta diagrammet nedan.

Inledande diagram

De starkt anslutna komponenterna i ovanstående diagram är:

Starkt anslutna komponenter

Du kan observera att i den första starkt anslutna komponenten kan varje topp nå den andra toppunkten genom den riktade vägen.

Dessa komponenter kan hittas med hjälp av Kosarajus algoritm .

Kosarajus algoritm

Kosarajus algoritm är baserad på den djup-första sökalgoritmen som implementerats två gånger.

Tre steg är inblandade.

Utför en djupgående sökning på hela grafen.
Låt oss börja från vertex-0, besöka alla dess underhörn och markera de besökta hörn som färdiga. Om ett vertex leder till ett redan besökt vertex, tryck sedan detta vertex till stacken.
Till exempel: Starta från vertex-0, gå till vertex-1, vertex-2 och sedan till vertex-3. Vertex-3 leder till redan besökt vertex-0, så tryck källpunkten (dvs. vertex-3) i stacken. DFS på diagrammet
Gå till föregående toppunkt (vertex-2) och besök dess barnhörn, dvs. vertex-4, vertex-5, vertex-6 och vertex-7 i följd. Eftersom det inte finns någonstans att gå från vertex-7, tryck in den i stacken. DFS i diagrammet
Gå till föregående toppunkt (vertex-6) och besök dess barnhörn. Men alla dess barnhörn besöks, så tryck in den i stacken. Stapling
På samma sätt skapas en slutlig stack. Sista stacken
Vänd originalgrafen. DFS på omvänd graf
Utför djup-första sökning på det omvända diagrammet.
Börja från toppens toppunkt. Korsa genom alla sina barnhörn. När det redan besökta toppunktet har uppnåtts, bildas en starkt ansluten komponent.
Till exempel: Pop vertex-0 från stacken. Från och med vertex-0, korsa genom sina barnhörn (vertex-0, vertex-1, vertex-2, vertex-3 i följd) och markera dem som besökta. Barnet till vertex-3 är redan besökt, så dessa besökta hörn utgör en starkt ansluten komponent. Börja uppifrån och korsa genom alla hörnpunkterna
Gå till stapeln och knäpp upp toppkanten om du redan har besökt. Annars väljer du det övre toppunktet från stapeln och går genom dess underordnade hörnpunkter enligt ovan. Pop upp toppkanten om du redan har besökt Starkt ansluten komponent
Således är de starkt anslutna komponenterna: Alla starkt anslutna komponenter

Python, Java, C ++ exempel

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