Hierholzerin algoritmi suunnatulle graafille
Suunnatun Eulerin graafin tehtävänä on tulostaa an Euler-piiri . Euler-piiri on polku, joka kulkee graafin jokaisen reunan läpi tarkalleen kerran ja polku päättyy aloituspisteeseen.
Huomautus: Annettu kaavio sisältää Euler-piirin.
Esimerkki:
Syöttö: Suunnattu graafi
Lähtö: 0 3 4 0 2 1 0
Edellytykset:
- Olemme keskustelleet mm ongelma sen selvittämisessä, onko tietty graafi Euler-kirjain vai ei ohjaamatonta kuvaajaa varten
- Euler-piirin ehdot suunnatussa grpagissa: (1) Kaikki kärjet kuuluvat yhteen vahvasti kytkeytyvään komponenttiin. (2) All vertices have same in-degree and out-degree. Huomaa, että suuntaamattomalle graafille ehto on erilainen (kaikilla pisteillä on parillinen aste)
Lähestyä:
- Valitse mikä tahansa aloituspiste v ja seuraa reunojen polkua tästä kärjestä palaamiseen v. Ei ole mahdollista juuttua mihinkään muuhun kärkeen kuin v, koska jokaisen kärjen in-asteen ja ulkoasteen tulee olla sama, kun polku tulee toiseen kärkeen w, w:stä tulee olla käyttämätön reuna. Tällä tavalla muodostettu kiertue on suljettu kiertomatka, mutta se ei välttämättä kata kaikkia alkuperäisen graafin huippuja ja reunoja.
- Niin kauan kuin on olemassa piste u, joka kuuluu nykyiseen kiertueeseen, mutta jolla on vierekkäisiä reunoja, jotka eivät kuulu kiertueeseen, aloita uusi polku u:sta käyttämättömien reunojen jälkeen palaamaan u:hun ja liitä näin muodostettu kiertomatka edelliseen kiertokulkuun.
Kuva:
Esimerkkinä yllä olevasta kaaviosta, jossa on 5 solmua: adj = {{2 3} {0} {1} {4} {0}}.
- Aloita kärjestä 0 :
- Nykyinen polku: [0]
- Piiri: []
- Piste 0 → 3 :
- Nykyinen polku: [0 3]
- Piiri: []
- Vertex 3 → 4 :
- Nykyinen polku: [0 3 4]
- Piiri: []
- Vertex 4 → 0 :
- Nykyinen polku: [0 3 4 0]
- Piiri: []
- Piste 0 → 2 :
- Nykyinen polku: [0 3 4 0 2]
- Piiri: []
- Vertex 2 → 1 :
- Nykyinen polku: [0 3 4 0 2 1]
- Piiri: []
- Vertex 1 → 0 :
- Nykyinen polku: [0 3 4 0 2 1 0]
- Piiri: []
- Palaa kärkeen 0 : Lisää 0 piiriin.
- Nykyinen polku: [0 3 4 0 2 1]
- Piiri: [0]
- Paluu kärkeen 1 : Lisää 1 piiriin.
- Nykyinen polku: [0 3 4 0 2]
- Piiri: [0 1]
- Palaa kärkeen 2 : Lisää 2 piiriin.
- Nykyinen polku: [0 3 4 0]
- Piiri: [0 1 2]
- Palaa kärkeen 0 : Lisää 0 piiriin.
- Nykyinen polku: [0 3 4]
- Piiri: [0 1 2 0]
- Palaa kärkeen 4 : Lisää 4 piiriin.
- Nykyinen polku: [0 3]
- Piiri: [0 1 2 0 4]
- Palaa kärkeen 3 : Lisää 3 piiriin.
- Nykyinen polku: [0]
- Piiri: [0 1 2 0 4 3]
- Palaa kärkeen 0 : Lisää 0 piiriin.
- Nykyinen polku: []
- Piiri: [0 1 2 0 4 3 0]
Alla on yllä olevan lähestymistavan toteutus:
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 ' ' ); }
Lähtö
0 3 4 0 2 1 0
Aika monimutkaisuus: O(V + E) missä V on pisteiden lukumäärä ja E on graafin reunojen lukumäärä. Syynä tähän on se, että algoritmi suorittaa syvyyshaun (DFS) ja vierailee jokaisessa kärjessä ja jokaisessa reunassa täsmälleen kerran. Jokaisen kärjen kohdalla kestää O(1) aikaa käydä siinä ja kunkin reunan läpi kulkemiseen kuluu O(1) aikaa.
Tilan monimutkaisuus: O(V + E), koska algoritmi käyttää pinoa tallentaakseen nykyisen polun ja listaa tallentaakseen lopullisen piirin. Pinon maksimikoko voi olla pahimmillaan V + E, joten tilan monimutkaisuus on O(V + E).
Luo tietokilpailu
