Componentes fuertemente conectados

Tabla de contenido

Algoritmo de Kosaraju
Ejemplos de Python, Java, C ++
Complejidad del algoritmo de Kosaraju
Aplicaciones de componentes fuertemente conectados

En este tutorial, aprenderá cómo se forman los componentes fuertemente conectados. Además, encontrará ejemplos prácticos del algoritmo de kosararju en C, C ++, Java y Python.

Un componente fuertemente conectado es la parte de un gráfico dirigido en el que hay una ruta de cada vértice a otro vértice. Es aplicable solo en un gráfico dirigido .

Por ejemplo:

Tomemos el siguiente gráfico.

Gráfico inicial

Los componentes fuertemente conectados del gráfico anterior son:

Componentes fuertemente conectados

Puede observar que en el primer componente fuertemente conectado, cada vértice puede alcanzar el otro vértice a través del camino dirigido.

Estos componentes se pueden encontrar utilizando el algoritmo de Kosaraju .

Algoritmo de Kosaraju

El algoritmo de Kosaraju se basa en el algoritmo de búsqueda de profundidad primero implementado dos veces.

Se trata de tres pasos.

Realice una primera búsqueda en profundidad en todo el gráfico.
Comencemos desde el vértice-0, visitemos todos sus vértices secundarios y marquemos los vértices visitados como hechos. Si un vértice conduce a un vértice ya visitado, empuje este vértice a la pila.
Por ejemplo: comenzando desde el vértice-0, vaya al vértice-1, al vértice-2 y luego al vértice-3. El vértice-3 lleva al vértice-0 ya visitado, así que inserte el vértice de origen (es decir, vértice-3) en la pila. DFS en el gráfico
Vaya al vértice anterior (vértice-2) y visite sus vértices secundarios, es decir, vértice-4, vértice-5, vértice-6 y vértice-7 secuencialmente. Como no hay ningún lugar adonde ir desde el vértice-7, empújelo hacia la pila. DFS en el gráfico
Vaya al vértice anterior (vértice-6) y visite sus vértices secundarios. Pero, se visitan todos sus vértices secundarios, así que empújelo en la pila. Apilamiento
De manera similar, se crea una pila final. Pila final
Invierta el gráfico original. DFS en gráfico invertido
Realice una búsqueda en profundidad en el gráfico invertido.
Empiece desde el vértice superior de la pila. Atraviesa todos sus vértices secundarios. Una vez que se alcanza el vértice ya visitado, se forma un componente fuertemente conectado.
Por ejemplo: Extraiga el vértice-0 de la pila. A partir del vértice-0, recorra sus vértices secundarios (vértice-0, vértice-1, vértice-2, vértice-3 en secuencia) y márquelos como visitados. El hijo del vértice-3 ya está visitado, por lo que estos vértices visitados forman un componente fuertemente conectado. Empiece desde arriba y recorra todos los vértices.
Vaya a la pila y haga estallar el vértice superior si ya lo ha visitado. De lo contrario, elija el vértice superior de la pila y atraviese sus vértices secundarios como se muestra arriba. Pop el vértice superior si ya lo ha visitado Componente fuertemente conectado
Por tanto, los componentes fuertemente conectados son: Todos los componentes fuertemente conectados

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