Hierholzers Algorithmus für gerichtete Graphen
Bei einem gerichteten Eulerschen Graphen besteht die Aufgabe darin, einen zu drucken Euler-Schaltung . Ein Euler-Kreis ist ein Pfad, der jede Kante eines Graphen genau einmal durchquert und am Startscheitelpunkt endet.
Notiz: Der angegebene Graph enthält einen Euler-Kreis.
Beispiel:
Eingabe: Gerichteter Graph
Ausgabe: 0 3 4 0 2 1 0
Voraussetzungen:
- Wir haben darüber gesprochen Problem, herauszufinden, ob ein gegebener Graph Eulersch ist oder nicht für einen ungerichteten Graphen
- Bedingungen für den Eulerkreis in einem gerichteten Grpag: (1) Alle Eckpunkte gehören zu einer einzelnen stark verbundenen Komponente. (2) Alle Scheitelpunkte haben den gleichen In-Grad und Out-Grad. Beachten Sie, dass die Bedingung für einen ungerichteten Graphen anders ist (alle Eckpunkte haben geraden Grad).
Ansatz:
- Wählen Sie einen beliebigen Startscheitelpunkt v und folgen Sie einer Spur von Kanten von diesem Scheitelpunkt aus, bis Sie zu v zurückkehren. Es ist nicht möglich, an einem anderen Scheitelpunkt als v stecken zu bleiben, da der Anfangs- und der Außengrad jedes Scheitelpunkts gleich sein müssen. Wenn die Spur in einen anderen Scheitelpunkt w eintritt, muss es eine ungenutzte Kante geben, die w verlässt. Die auf diese Weise gebildete Tour ist eine geschlossene Tour, deckt jedoch möglicherweise nicht alle Eckpunkte und Kanten des ursprünglichen Diagramms ab.
- Solange es einen Scheitelpunkt u gibt, der zur aktuellen Tour gehört, aber angrenzende Kanten hat, die nicht Teil der Tour sind, beginne einen weiteren Pfad von u aus, folge ungenutzten Kanten bis zurück zu u und verbinde die so gebildete Tour mit der vorherigen Tour.
Illustration:
Nehmen wir als Beispiel das obige Diagramm mit 5 Knoten: adj = {{2 3} {0} {1} {4} {0}}.
- Beginnen Sie am Scheitelpunkt 0 :
- Aktueller Pfad: [0]
- Schaltung: []
- Scheitelpunkt 0 → 3 :
- Aktueller Pfad: [0 3]
- Schaltung: []
- Scheitelpunkt 3 → 4 :
- Aktueller Pfad: [0 3 4]
- Schaltung: []
- Scheitelpunkt 4 → 0 :
- Aktueller Pfad: [0 3 4 0]
- Schaltung: []
- Scheitelpunkt 0 → 2 :
- Aktueller Pfad: [0 3 4 0 2]
- Schaltung: []
- Scheitelpunkt 2 → 1 :
- Aktueller Pfad: [0 3 4 0 2 1]
- Schaltung: []
- Scheitelpunkt 1 → 0 :
- Aktueller Pfad: [0 3 4 0 2 1 0]
- Schaltung: []
- Zurück zum Scheitelpunkt 0 : 0 zur Schaltung hinzufügen.
- Aktueller Pfad: [0 3 4 0 2 1]
- Schaltung: [0]
- Zurück zum Scheitelpunkt 1 : Addiere 1 zur Schaltung.
- Aktueller Pfad: [0 3 4 0 2]
- Schaltung: [0 1]
- Zurück zum Scheitelpunkt 2 : Addiere 2 zur Schaltung.
- Aktueller Pfad: [0 3 4 0]
- Schaltung: [0 1 2]
- Zurück zum Scheitelpunkt 0 : 0 zur Schaltung hinzufügen.
- Aktueller Pfad: [0 3 4]
- Schaltung: [0 1 2 0]
- Zurück zum Scheitelpunkt 4 : Addiere 4 zum Stromkreis.
- Aktueller Pfad: [0 3]
- Schaltung: [0 1 2 0 4]
- Zurück zum Scheitelpunkt 3 : Addiere 3 zur Schaltung.
- Aktueller Pfad: [0]
- Schaltung: [0 1 2 0 4 3]
- Zurück zum Scheitelpunkt 0 : 0 zur Schaltung hinzufügen.
- Aktueller Pfad: []
- Schaltung: [0 1 2 0 4 3 0]
Nachfolgend finden Sie die Implementierung für den oben genannten Ansatz:
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 ' ' ); }
Ausgabe
0 3 4 0 2 1 0
Zeitkomplexität: O(V + E) wobei V die Anzahl der Eckpunkte und E die Anzahl der Kanten im Diagramm ist. Der Grund dafür ist, dass der Algorithmus eine Tiefensuche (DFS) durchführt und jeden Scheitelpunkt und jede Kante genau einmal besucht. Es dauert also für jeden Scheitelpunkt O(1) Zeit, ihn zu besuchen, und für jede Kante dauert es O(1) Zeit, ihn zu durchlaufen.
Raumkomplexität: O(V + E), da der Algorithmus einen Stapel zum Speichern des aktuellen Pfads und eine Liste zum Speichern des endgültigen Schaltkreises verwendet. Die maximale Größe des Stapels kann im schlimmsten Fall V + E betragen, sodass die Raumkomplexität O(V + E) beträgt.
Quiz erstellen
