Algorithme de Hierholzer pour graphe orienté
Étant donné un graphe eulérien orienté, la tâche consiste à imprimer un Circuit d'Euler . Un circuit d'Euler est un chemin qui traverse chaque arête d'un graphe exactement une fois et le chemin se termine au sommet de départ.
Note: Le graphique donné contient un circuit d'Euler.
Exemple:
Entrée : Graphe orienté
Sortir: 0 3 4 0 2 1 0
Prérequis :
- Nous avons discuté du problème de savoir si un graphe donné est eulérien ou non pour un graphe non orienté
- Conditions pour un circuit eulérien dans un Grpag dirigé : (1) Tous les sommets appartiennent à une seule composante fortement connectée. (2) Tous les sommets ont le même degré d'entrée et de sortie. Notez que pour un graphe non orienté, la condition est différente (tous les sommets ont un degré pair)
Approche:
- Choisissez n'importe quel sommet de départ v et suivez une trace d'arêtes à partir de ce sommet jusqu'à revenir à v. Il n'est pas possible de rester bloqué à un sommet autre que v car le degré d'entrée et de sortie de chaque sommet doit être le même lorsque la trace entre dans un autre sommet w, il doit y avoir une arête inutilisée quittant w. Le tour ainsi formé est un tour fermé mais peut ne pas couvrir tous les sommets et arêtes du graphe initial.
- Tant qu'il existe un sommet u qui appartient au tour en cours mais qui a des arêtes adjacentes ne faisant pas partie du tour, commencer un autre sentier à partir de u en suivant les arêtes inutilisées jusqu'à revenir à u et rejoindre le tour ainsi formé au tour précédent.
Illustration:
Prenant exemple du graphe ci-dessus à 5 nœuds : adj = {{2 3} {0} {1} {4} {0}}.
- Commencer au sommet 0 :
- Chemin actuel : [0]
- Circuit : []
- Sommet 0 → 3 :
- Chemin actuel : [0 3]
- Circuit : []
- Sommet 3 → 4 :
- Chemin actuel : [0 3 4]
- Circuit : []
- Sommet 4 → 0 :
- Chemin actuel : [0 3 4 0]
- Circuit : []
- Sommet 0 → 2 :
- Chemin actuel : [0 3 4 0 2]
- Circuit : []
- Sommet 2 → 1 :
- Chemin actuel : [0 3 4 0 2 1]
- Circuit : []
- Sommet 1 → 0 :
- Chemin actuel : [0 3 4 0 2 1 0]
- Circuit : []
- Revenir au sommet 0 : Ajoutez 0 au circuit.
- Chemin actuel : [0 3 4 0 2 1]
- Circuit : [0]
- Revenir au sommet 1 : Ajoutez 1 au circuit.
- Chemin actuel : [0 3 4 0 2]
- Circuit : [0 1]
- Revenir au sommet 2 : Ajoutez 2 au circuit.
- Chemin actuel : [0 3 4 0]
- Circuit : [0 1 2]
- Revenir au sommet 0 : Ajoutez 0 au circuit.
- Chemin actuel : [0 3 4]
- Circuit : [0 1 2 0]
- Revenir au sommet 4 : Ajoutez 4 au circuit.
- Chemin actuel : [0 3]
- Circuit : [0 1 2 0 4]
- Revenir au sommet 3 : Ajoutez 3 au circuit.
- Chemin actuel : [0]
- Circuit : [0 1 2 0 4 3]
- Revenir au sommet 0 : Ajoutez 0 au circuit.
- Chemin actuel : []
- Circuit : [0 1 2 0 4 3 0]
Vous trouverez ci-dessous la mise en œuvre de l'approche ci-dessus :
C++ // C++ program to print Eulerian circuit in given // directed graph using Hierholzer algorithm #include using namespace std ; // Function to print Eulerian circuit vector < int > printCircuit ( vector < vector < int >> & adj ) { int n = adj . size (); if ( n == 0 ) return {}; // Maintain a stack to keep vertices // We can start from any vertex here we start with 0 vector < int > currPath ; currPath . push_back ( 0 ); // list to store final circuit vector < int > circuit ; while ( currPath . size () > 0 ) { int currNode = currPath [ currPath . size () - 1 ]; // If there's remaining edge in adjacency list // of the current vertex if ( adj [ currNode ]. size () > 0 ) { // Find and remove the next vertex that is // adjacent to the current vertex int nextNode = adj [ currNode ]. back (); adj [ currNode ]. pop_back (); // Push the new vertex to the stack currPath . push_back ( nextNode ); } // back-track to find remaining circuit else { // Remove the current vertex and // put it in the circuit circuit . push_back ( currPath . back ()); currPath . pop_back (); } } // reverse the result vector reverse ( circuit . begin () circuit . end ()); return circuit ; } int main () { vector < vector < int >> adj = {{ 2 3 } { 0 } { 1 } { 4 } { 0 }}; vector < int > ans = printCircuit ( adj ); for ( auto v : ans ) cout < < v < < ' ' ; cout < < endl ; return 0 ; }
Java // Java program to print Eulerian circuit in given // directed graph using Hierholzer algorithm import java.util.* ; class GfG { // Function to print Eulerian circuit static List < Integer > printCircuit ( List < List < Integer >> adj ) { int n = adj . size (); if ( n == 0 ) return new ArrayList <> (); // Maintain a stack to keep vertices // We can start from any vertex here we start with 0 List < Integer > currPath = new ArrayList <> (); currPath . add ( 0 ); // list to store final circuit List < Integer > circuit = new ArrayList <> (); while ( currPath . size () > 0 ) { int currNode = currPath . get ( currPath . size () - 1 ); // If there's remaining edge in adjacency list // of the current vertex if ( adj . get ( currNode ). size () > 0 ) { // Find and remove the next vertex that is // adjacent to the current vertex int nextNode = adj . get ( currNode ). get ( adj . get ( currNode ). size () - 1 ); adj . get ( currNode ). remove ( adj . get ( currNode ). size () - 1 ); // Push the new vertex to the stack currPath . add ( nextNode ); } // back-track to find remaining circuit else { // Remove the current vertex and // put it in the circuit circuit . add ( currPath . get ( currPath . size () - 1 )); currPath . remove ( currPath . size () - 1 ); } } // reverse the result vector Collections . reverse ( circuit ); return circuit ; } public static void main ( String [] args ) { List < List < Integer >> adj = new ArrayList <> (); adj . add ( new ArrayList <> ( Arrays . asList ( 2 3 ))); adj . add ( new ArrayList <> ( Arrays . asList ( 0 ))); adj . add ( new ArrayList <> ( Arrays . asList ( 1 ))); adj . add ( new ArrayList <> ( Arrays . asList ( 4 ))); adj . add ( new ArrayList <> ( Arrays . asList ( 0 ))); List < Integer > ans = printCircuit ( adj ); for ( int v : ans ) System . out . print ( v + ' ' ); System . out . println (); } }
Python # Python program to print Eulerian circuit in given # directed graph using Hierholzer algorithm # Function to print Eulerian circuit def printCircuit ( adj ): n = len ( adj ) if n == 0 : return [] # Maintain a stack to keep vertices # We can start from any vertex here we start with 0 currPath = [ 0 ] # list to store final circuit circuit = [] while len ( currPath ) > 0 : currNode = currPath [ - 1 ] # If there's remaining edge in adjacency list # of the current vertex if len ( adj [ currNode ]) > 0 : # Find and remove the next vertex that is # adjacent to the current vertex nextNode = adj [ currNode ] . pop () # Push the new vertex to the stack currPath . append ( nextNode ) # back-track to find remaining circuit else : # Remove the current vertex and # put it in the circuit circuit . append ( currPath . pop ()) # reverse the result vector circuit . reverse () return circuit if __name__ == '__main__' : adj = [[ 2 3 ] [ 0 ] [ 1 ] [ 4 ] [ 0 ]] ans = printCircuit ( adj ) for v in ans : print ( v end = ' ' ) print ()
C# // C# program to print Eulerian circuit in given // directed graph using Hierholzer algorithm using System ; using System.Collections.Generic ; class GfG { // Function to print Eulerian circuit static List < int > printCircuit ( List < List < int >> adj ) { int n = adj . Count ; if ( n == 0 ) return new List < int > (); // Maintain a stack to keep vertices // We can start from any vertex here we start with 0 List < int > currPath = new List < int > { 0 }; // list to store final circuit List < int > circuit = new List < int > (); while ( currPath . Count > 0 ) { int currNode = currPath [ currPath . Count - 1 ]; // If there's remaining edge in adjacency list // of the current vertex if ( adj [ currNode ]. Count > 0 ) { // Find and remove the next vertex that is // adjacent to the current vertex int nextNode = adj [ currNode ][ adj [ currNode ]. Count - 1 ]; adj [ currNode ]. RemoveAt ( adj [ currNode ]. Count - 1 ); // Push the new vertex to the stack currPath . Add ( nextNode ); } // back-track to find remaining circuit else { // Remove the current vertex and // put it in the circuit circuit . Add ( currPath [ currPath . Count - 1 ]); currPath . RemoveAt ( currPath . Count - 1 ); } } // reverse the result vector circuit . Reverse (); return circuit ; } static void Main ( string [] args ) { List < List < int >> adj = new List < List < int >> { new List < int > { 2 3 } new List < int > { 0 } new List < int > { 1 } new List < int > { 4 } new List < int > { 0 } }; List < int > ans = printCircuit ( adj ); foreach ( int v in ans ) { Console . Write ( v + ' ' ); } Console . WriteLine (); } }
JavaScript // JavaScript program to print Eulerian circuit in given // directed graph using Hierholzer algorithm // Function to print Eulerian circuit function printCircuit ( adj ) { let n = adj . length ; if ( n === 0 ) return []; // Maintain a stack to keep vertices // We can start from any vertex here we start with 0 let currPath = [ 0 ]; // list to store final circuit let circuit = []; while ( currPath . length > 0 ) { let currNode = currPath [ currPath . length - 1 ]; // If there's remaining edge in adjacency list // of the current vertex if ( adj [ currNode ]. length > 0 ) { // Find and remove the next vertex that is // adjacent to the current vertex let nextNode = adj [ currNode ]. pop (); // Push the new vertex to the stack currPath . push ( nextNode ); } // back-track to find remaining circuit else { // Remove the current vertex and // put it in the circuit circuit . push ( currPath . pop ()); } } // reverse the result vector circuit . reverse (); return circuit ; } let adj = [[ 2 3 ] [ 0 ] [ 1 ] [ 4 ] [ 0 ]]; let ans = printCircuit ( adj ); for ( let v of ans ) { console . log ( v ' ' ); }
Sortir
0 3 4 0 2 1 0
Complexité temporelle : O(V + E) où V est le nombre de sommets et E est le nombre d'arêtes du graphe. La raison en est que l’algorithme effectue une recherche en profondeur (DFS) et visite chaque sommet et chaque arête exactement une fois. Ainsi, pour chaque sommet, il faut un temps O(1) pour le visiter et pour chaque arête, il faut un temps O(1) pour le parcourir.
Complexité spatiale : O(V + E) car l'algorithme utilise une pile pour stocker le chemin actuel et une liste pour stocker le circuit final. La taille maximale de la pile peut être au pire V + E donc la complexité spatiale est O (V + E).
Créer un quiz
