Hierholzerjev algoritem za usmerjeni graf
Glede na usmerjen Eulerjev graf je naloga natisniti Eulerjevo vezje . Eulerjevo vezje je pot, ki prečka vsak rob grafa natanko enkrat in se pot konča na začetni točki.
Opomba: Dani graf vsebuje Eulerjevo vezje.
primer:
Vhod: usmerjeni graf
Izhod: 0 3 4 0 2 1 0
Predpogoji:
- Razpravljali smo o problem ugotavljanja, ali je dani graf Eulerjev ali ne za neusmerjen graf
- Pogoji za Eulerjevo vezje v usmerjenem grpagu: (1) Vsa vozlišča pripadajo eni sami močno povezani komponenti. (2) Vsa oglišča imajo enako notranjo in izhodno stopnjo. Upoštevajte, da je za neusmerjeni graf pogoj drugačen (vsa oglišča imajo sodo stopnjo)
Pristop:
- Izberite poljubno začetno točko v in sledite vrsti robov od te točke do vrnitve v v. Ni mogoče, da bi se zataknili pri kateri koli točki, razen v, ker morata biti vhodna in izhodna stopnja vsake točke enaki, ko sled vstopi v drugo točko w, mora biti neuporabljen rob, ki zapušča w. Tako oblikovana tura je zaprta tura, vendar morda ne pokriva vseh oglišč in robov začetnega grafa.
- Dokler obstaja vozlišče u, ki pripada trenutni turi, vendar ima sosednje robove, ki niso del ture, začnite drugo sled od u po neuporabljenih robovih do vrnitve v u in tako oblikovano turo pridružite prejšnji turi.
Ilustracija:
Če vzamemo primer zgornjega grafa s 5 vozlišči: adj = {{2 3} {0} {1} {4} {0}}.
- Začnite pri točki 0 :
- Trenutna pot: [0]
- Krog: []
- Točka 0 → 3 :
- Trenutna pot: [0 3]
- Krog: []
- Vertex 3 → 4 :
- Trenutna pot: [0 3 4]
- Krog: []
- Točka 4 → 0 :
- Trenutna pot: [0 3 4 0]
- Krog: []
- Točka 0 → 2 :
- Trenutna pot: [0 3 4 0 2]
- Krog: []
- Vertex 2 → 1 :
- Trenutna pot: [0 3 4 0 2 1]
- Krog: []
- Točka 1 → 0 :
- Trenutna pot: [0 3 4 0 2 1 0]
- Krog: []
- Nazaj na točko 0 : vezju dodajte 0.
- Trenutna pot: [0 3 4 0 2 1]
- Krog: [0]
- Nazaj na točko 1 : dodajte 1 vezju.
- Trenutna pot: [0 3 4 0 2]
- Krog: [0 1]
- Nazaj na točko 2 : Dodajte 2 v vezje.
- Trenutna pot: [0 3 4 0]
- Krog: [0 1 2]
- Nazaj na točko 0 : vezju dodajte 0.
- Trenutna pot: [0 3 4]
- Krog: [0 1 2 0]
- Nazaj na točko 4 : dodajte 4 krogu.
- Trenutna pot: [0 3]
- Krog: [0 1 2 0 4]
- Nazaj na točko 3 : dodajte 3 krogu.
- Trenutna pot: [0]
- Krog: [0 1 2 0 4 3]
- Nazaj na točko 0 : vezju dodajte 0.
- Trenutna pot: []
- Krog: [0 1 2 0 4 3 0]
Spodaj je izvedba za zgornji pristop:
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 ' ' ); }
Izhod
0 3 4 0 2 1 0
Časovna zapletenost: O(V + E), kjer je V število vozlišč in E število robov v grafu. Razlog za to je, ker algoritem izvede iskanje najprej v globino (DFS) in obišče vsako točko in vsak rob natanko enkrat. Torej za vsako vozlišče potrebuje O(1) časa, da ga obišče in za vsak rob potrebuje O(1) časa, da ga prečka.
Kompleksnost prostora : O(V + E) kot algoritem uporablja sklad za shranjevanje trenutne poti in seznam za shranjevanje končnega vezja. Največja velikost sklada je lahko v najslabšem primeru V + E, tako da je kompleksnost prostora O(V + E).
Ustvari kviz
