Composants fortement connectés

Table des matières

Algorithme de Kosaraju
Exemples Python, Java, C ++
Complexité de l'algorithme de Kosaraju
Applications de composants fortement connectés

Dans ce didacticiel, vous apprendrez à quel point les composants fortement connectés sont formés. Vous trouverez également des exemples fonctionnels de l'algorithme de kosararju en C, C ++, Java et Python.

Un composant fortement connecté est la partie d'un graphe orienté dans laquelle il y a un chemin de chaque sommet à un autre sommet. Il n'est applicable que sur un graphe orienté .

Par exemple:

Prenons le graphique ci-dessous.

Graphique initial

Les composants fortement connectés du graphique ci-dessus sont:

Des composants fortement connectés

Vous pouvez observer que dans le premier composant fortement connecté, chaque sommet peut atteindre l'autre sommet par le chemin dirigé.

Ces composants peuvent être trouvés en utilisant l' algorithme de Kosaraju .

Algorithme de Kosaraju

L'algorithme de Kosaraju est basé sur l'algorithme de recherche en profondeur d'abord implémenté deux fois.

Trois étapes sont impliquées.

Effectuez une première recherche en profondeur sur l'ensemble du graphique.
Commençons par le sommet-0, visitons tous ses sommets enfants et marquons les sommets visités comme terminés. Si un sommet mène à un sommet déjà visité, poussez ce sommet vers la pile.
Par exemple: à partir du sommet-0, allez au sommet-1, au sommet-2, puis au sommet-3. Le sommet-3 mène au sommet-0 déjà visité, donc poussez le sommet source (c'est-à-dire le sommet-3) dans la pile. DFS sur le graphe
Aller au sommet précédent (sommet-2) et visiter ses sommets enfants, c'est-à-dire sommet-4, sommet-5, sommet-6 et sommet-7 séquentiellement. Puisqu'il n'y a nulle part où aller du sommet-7, poussez-le dans la pile. DFS sur le graphique
Allez au sommet précédent (vertex-6) et visitez ses sommets enfants. Mais, tous ses sommets enfants sont visités, alors poussez-le dans la pile. Empilement
De même, une pile finale est créée. Pile finale
Inversez le graphique d'origine. DFS sur graphique inversé
Effectuez une recherche en profondeur d'abord sur le graphique inversé.
Commencez par le sommet supérieur de la pile. Traverse tous ses sommets enfants. Une fois que le sommet déjà visité est atteint, un composant fortement connecté est formé.
Par exemple: Pop vertex-0 de la pile. À partir du sommet-0, traversez ses sommets enfants (sommet-0, sommet-1, sommet-2, sommet-3 en séquence) et marquez-les comme visités. L'enfant du vertex-3 est déjà visité, donc ces sommets visités forment un composant fortement connecté. Commencez par le haut et traversez tous les sommets.
Accédez à la pile et sautez le sommet supérieur s'il est déjà visité. Sinon, choisissez le sommet supérieur de la pile et traversez ses sommets enfants comme indiqué ci-dessus. Pop le sommet supérieur s'il est déjà visité Composant fortement connecté
Ainsi, les composants fortement connectés sont: Tous les composants fortement connectés

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