Componenti fortemente connessi

Sommario

Algoritmo di Kosaraju
Esempi di Python, Java, C ++
Complessità dell'algoritmo di Kosaraju
Applicazioni di componenti fortemente connesse

In questo tutorial imparerai come si formano i componenti fortemente connessi. Inoltre, troverai esempi funzionanti dell'algoritmo di kosararju in C, C ++, Java e Python.

Un componente fortemente connesso è la porzione di un grafo orientato in cui c'è un percorso da ogni vertice a un altro vertice. È applicabile solo su un grafico diretto .

Per esempio:

Prendiamo il grafico qui sotto.

Grafico iniziale

Le componenti fortemente connesse del grafico sopra sono:

Componenti fortemente collegati

Si può osservare che nella prima componente fortemente connessa, ogni vertice può raggiungere l'altro vertice attraverso il percorso diretto.

Questi componenti possono essere trovati usando l' algoritmo di Kosaraju .

Algoritmo di Kosaraju

L'algoritmo di Kosaraju si basa sull'algoritmo di ricerca in profondità implementato due volte.

Sono coinvolti tre passaggi.

Eseguire una prima ricerca approfondita sull'intero grafico.
Cominciamo dal vertice-0, visitiamo tutti i suoi vertici figli e contrassegniamo i vertici visitati come completati. Se un vertice porta a un vertice già visitato, spingere questo vertice nella pila.
Ad esempio: a partire dal vertice-0, vai al vertice-1, al vertice-2 e quindi al vertice-3. Il vertice-3 porta al vertice-0 già visitato, quindi inserisci il vertice sorgente (cioè il vertice-3) nella pila. DFS sul grafico
Vai al vertice precedente (vertice-2) e visita i suoi vertici figli cioè vertice-4, vertice-5, vertice-6 e vertice-7 in sequenza. Poiché non c'è nessun posto dove andare dal vertice-7, inseriscilo nella pila. DFS sul grafico
Vai al vertice precedente (vertice-6) e visita i suoi vertici figli. Tuttavia, tutti i suoi vertici figlio vengono visitati, quindi inseriscilo nello stack. Stacking
Allo stesso modo, viene creato uno stack finale. Stack finale
Inverti il grafico originale. DFS sul grafico invertito
Eseguire una ricerca in profondità sul grafico invertito.
Inizia dal vertice superiore della pila. Attraversa tutti i suoi vertici figlio. Una volta raggiunto il vertice già visitato, si forma una componente fortemente connessa.
Ad esempio: Pop vertex-0 dallo stack. Partendo dal vertice-0, attraversa i suoi vertici figli (vertice-0, vertice-1, vertice-2, vertice-3 in sequenza) e contrassegnali come visitati. Il figlio del vertice-3 è già visitato, quindi questi vertici visitati formano un componente fortemente connesso. Inizia dall'alto e attraversa tutti i vertici
Vai alla pila e fai apparire il vertice superiore se già visitato. Altrimenti, scegli il vertice superiore dalla pila e attraversa i suoi vertici figli come presentato sopra. Apri il vertice superiore se già visitato Componente fortemente connesso
Pertanto, i componenti fortemente connessi sono: Tutti i componenti fortemente connessi

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