Componentes fortemente conectados

Índice

Algoritmo de Kosaraju
Exemplos de Python, Java, C ++
Complexidade de Algoritmo de Kosaraju
Aplicativos de componentes fortemente conectados

Neste tutorial, você aprenderá como os componentes fortemente conectados são formados. Além disso, você encontrará exemplos de funcionamento do algoritmo de kosararju em C, C ++, Java e Python.

Um componente fortemente conectado é a parte de um gráfico direcionado em que há um caminho de cada vértice para outro vértice. É aplicável apenas em um gráfico direcionado .

Por exemplo:

Deixe-nos ver o gráfico abaixo.

Gráfico inicial

Os componentes fortemente conectados do gráfico acima são:

Componentes fortemente conectados

Você pode observar que no primeiro componente fortemente conectado, cada vértice pode alcançar o outro vértice através do caminho direcionado.

Esses componentes podem ser encontrados usando o Algoritmo de Kosaraju .

Algoritmo de Kosaraju

O Algoritmo de Kosaraju é baseado no algoritmo de busca em profundidade implementado duas vezes.

Três etapas estão envolvidas.

Realize uma primeira pesquisa em profundidade em todo o gráfico.
Vamos começar a partir do vértice-0, visitar todos os seus vértices filhos e marcar os vértices visitados como concluídos. Se um vértice leva a um vértice já visitado, empurre esse vértice para a pilha.
Por exemplo: começando do vértice-0, vá para o vértice-1, vértice-2 e, a seguir, para o vértice-3. O vértice-3 leva ao vértice-0 já visitado, então empurre o vértice de origem (ou seja, vértice-3) na pilha. DFS no gráfico
Vá para o vértice anterior (vértice-2) e visite seus vértices filhos, isto é, vértice-4, vértice-5, vértice-6 e vértice-7 sequencialmente. Como não há nenhum lugar para ir do vértice 7, empurre-o para a pilha. DFS no gráfico
Vá para o vértice anterior (vértice-6) e visite seus vértices filhos. Mas, todos os seus vértices filhos são visitados, então coloque-o na pilha. Empilhamento
Da mesma forma, uma pilha final é criada. Pilha Final
Inverta o gráfico original. DFS no gráfico invertido
Execute a pesquisa em profundidade no gráfico invertido.
Comece do vértice superior da pilha. Percorra todos os seus vértices filhos. Uma vez que o vértice já visitado é alcançado, um componente fortemente conectado é formado.
Por exemplo: Retire o vértice-0 da pilha. A partir do vértice-0, atravesse seus vértices filhos (vértice-0, vértice-1, vértice-2, vértice-3 em sequência) e marque-os como visitados. O filho do vértice-3 já foi visitado, então esses vértices visitados formam um componente fortemente conectado. Comece do topo e atravesse todos os vértices.
Vá para a pilha e abra o vértice superior se já visitado. Caso contrário, escolha o vértice superior da pilha e atravesse seus vértices filhos, conforme apresentado acima. Pop o vértice superior se já visitado Componente fortemente conectado
Assim, os componentes fortemente conectados são: Todos os componentes fortemente conectados

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