Hierholzers algoritm för riktad graf
Givet en riktad Eulerisk graf är uppgiften att skriva ut en Euler krets . En Euler-krets är en bana som korsar varje kant av en graf exakt en gång och banan slutar på startpunkten.
Notera: Den givna grafen innehåller en Euler-krets.
Exempel:
Ingång: Riktad graf
Produktion: 0 3 4 0 2 1 0
Förutsättningar:
- Vi har diskuterat problem med att ta reda på om en given graf är Eulerian eller inte för en oriktad graf
- Villkor för Eulerisk krets i en riktad Grpag: (1) Alla hörn tillhör en enda starkt ansluten komponent. (2) Alla hörn har samma in-grad och ut-grad. Observera att för en oriktad graf är villkoret annorlunda (alla hörn har jämn grad)
Närma sig:
- Välj vilken startpunkt v som helst och följ ett spår av kanter från den hörn tills du återvänder till v. Det är inte möjligt att fastna vid någon annan vinkel än v eftersom ingrad och ograd av varje vertex måste vara samma när leden går in i en annan vertex w det måste finnas en oanvänd kant som lämnar w. Turen som bildas på det här sättet är en sluten tur men täcker kanske inte alla hörn och kanter på den ursprungliga grafen.
- Så länge det finns en vertex u som hör till den aktuella turen men som har intilliggande kanter som inte är en del av turen, starta ett annat spår från att du följer oanvända kanter tills du återvänder till u och ansluter den tur som bildas på detta sätt till den föregående turen.
Illustration:
Ta ett exempel på grafen ovan med 5 noder: adj = {{2 3} {0} {1} {4} {0}}.
- Börja vid toppunkt 0 :
- Aktuell väg: [0]
- Krets: []
- Vertex 0 → 3 :
- Aktuell väg: [0 3]
- Krets: []
- Vertex 3 → 4 :
- Aktuell väg: [0 3 4]
- Krets: []
- Vertex 4 → 0 :
- Aktuell väg: [0 3 4 0]
- Krets: []
- Vertex 0 → 2 :
- Aktuell väg: [0 3 4 0 2]
- Krets: []
- Vertex 2 → 1 :
- Aktuell väg: [0 3 4 0 2 1]
- Krets: []
- Vertex 1 → 0 :
- Aktuell väg: [0 3 4 0 2 1 0]
- Krets: []
- Gå tillbaka till vertex 0 : Lägg till 0 till kretsen.
- Aktuell väg: [0 3 4 0 2 1]
- Krets: [0]
- Gå tillbaka till vertex 1 : Lägg till 1 till kretsen.
- Aktuell väg: [0 3 4 0 2]
- Krets: [0 1]
- Gå tillbaka till vertex 2 : Lägg till 2 till kretsen.
- Aktuell väg: [0 3 4 0]
- Krets: [0 1 2]
- Gå tillbaka till vertex 0 : Lägg till 0 till kretsen.
- Aktuell väg: [0 3 4]
- Krets: [0 1 2 0]
- Gå tillbaka till vertex 4 : Lägg till 4 till kretsen.
- Aktuell väg: [0 3]
- Krets: [0 1 2 0 4]
- Tillbaka till vertex 3 : Lägg till 3 till kretsen.
- Aktuell väg: [0]
- Krets: [0 1 2 0 4 3]
- Gå tillbaka till vertex 0 : Lägg till 0 till kretsen.
- Aktuell väg: []
- Krets: [0 1 2 0 4 3 0]
Nedan är implementeringen av ovanstående tillvägagångssätt:
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 ' ' ); }
Produktion
0 3 4 0 2 1 0
Tidskomplexitet: O(V + E) där V är antalet hörn och E är antalet kanter i grafen. Anledningen till detta är att algoritmen utför en djup-först-sökning (DFS) och besöker varje vertex och varje kant exakt en gång. Så för varje vertex tar det O(1) tid att besöka den och för varje kant tar det O(1) tid att korsa den.
Rymdkomplexitet: O(V + E) eftersom algoritmen använder en stack för att lagra den aktuella vägen och en lista för att lagra den slutliga kretsen. Den maximala storleken på stacken kan vara V + E i värsta fall så rymdkomplexiteten är O(V + E).
Skapa frågesport
