Algorytm Hierholzera dla grafu skierowanego
Mając skierowany graf Eulera, zadaniem jest wydrukowanie Obwód Eulera . Obwód Eulera to droga, która przechodzi przez każdą krawędź grafu dokładnie raz i kończy się w wierzchołku początkowym.
Notatka: Podany graf zawiera obwód Eulera.
Przykład:
Dane wejściowe: Wykres skierowany
Wyjście: 0 3 4 0 2 1 0
Warunki wstępne:
- Omówiliśmy problem sprawdzenia, czy dany graf jest eulerowski, czy nie dla grafu nieskierowanego
- Warunki dla obwodu Eulera w grupie skierowanej: (1) Wszystkie wierzchołki należą do jednego, silnie połączonego elementu. (2) Wszystkie wierzchołki mają ten sam stopień wejściowy i wyjściowy. Zauważ, że dla grafu nieskierowanego warunek jest inny (wszystkie wierzchołki mają parzysty stopień)
Zbliżać się:
- Wybierz dowolny początkowy wierzchołek v i podążaj śladem krawędzi od tego wierzchołka, aż powrócisz do v. Nie jest możliwe utknięcie w żadnym wierzchołku innym niż v, ponieważ stopień początkowy i stopień wyjściowy każdego wierzchołka muszą być takie same, gdy szlak wchodzi w inny wierzchołek w, musi istnieć niewykorzystana krawędź opuszczająca w. Utworzona w ten sposób trasa jest trasą zamkniętą, ale może nie obejmować wszystkich wierzchołków i krawędzi początkowego wykresu.
- Tak długo, jak istnieje wierzchołek u, który należy do bieżącej trasy, ale ma sąsiadujące krawędzie, które nie są częścią trasy, rozpocznij kolejny szlak od u, podążając za nieużywanymi krawędziami, aż do powrotu do ciebie i dołącz utworzoną w ten sposób trasę do poprzedniej trasy.
Ilustracja:
Biorąc przykład z powyższego wykresu z 5 węzłami: adj = {{2 3} {0} {1} {4} {0}}.
- Zacznij od wierzchołka 0 :
- Bieżąca ścieżka: [0]
- Okrążenie: []
- Wierzchołek 0 → 3 :
- Bieżąca ścieżka: [0 3]
- Okrążenie: []
- Wierzchołek 3 → 4 :
- Bieżąca ścieżka: [0 3 4]
- Okrążenie: []
- Wierzchołek 4 → 0 :
- Bieżąca ścieżka: [0 3 4 0]
- Okrążenie: []
- Wierzchołek 0 → 2 :
- Bieżąca ścieżka: [0 3 4 0 2]
- Okrążenie: []
- Wierzchołek 2 → 1 :
- Bieżąca ścieżka: [0 3 4 0 2 1]
- Okrążenie: []
- Wierzchołek 1 → 0 :
- Bieżąca ścieżka: [0 3 4 0 2 1 0]
- Okrążenie: []
- Powrót do wierzchołka 0 : Dodaj 0 do obwodu.
- Bieżąca ścieżka: [0 3 4 0 2 1]
- Obwód: [0]
- Powrót do wierzchołka 1 : Dodaj 1 do obwodu.
- Bieżąca ścieżka: [0 3 4 0 2]
- Obwód: [0 1]
- Powrót do wierzchołka 2 : Dodaj 2 do obwodu.
- Bieżąca ścieżka: [0 3 4 0]
- Obwód: [0 1 2]
- Powrót do wierzchołka 0 : Dodaj 0 do obwodu.
- Bieżąca ścieżka: [0 3 4]
- Obwód: [0 1 2 0]
- Powrót do wierzchołka 4 : Dodaj 4 do obwodu.
- Bieżąca ścieżka: [0 3]
- Obwód: [0 1 2 0 4]
- Powrót do wierzchołka 3 : Dodaj 3 do obwodu.
- Bieżąca ścieżka: [0]
- Obwód: [0 1 2 0 4 3]
- Powrót do wierzchołka 0 : Dodaj 0 do obwodu.
- Bieżąca ścieżka: []
- Obwód: [0 1 2 0 4 3 0]
Poniżej implementacja powyższego podejścia:
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 ' ' ); }
Wyjście
0 3 4 0 2 1 0
Złożoność czasowa: O(V + E) gdzie V to liczba wierzchołków, a E to liczba krawędzi grafu. Dzieje się tak dlatego, że algorytm przeprowadza przeszukiwanie w głąb (DFS) i odwiedza każdy wierzchołek i każdą krawędź dokładnie raz. Zatem dla każdego wierzchołka potrzeba O(1) czasu, aby go odwiedzić, a dla każdej krawędzi potrzeba O(1) czasu, aby go przejść.
Złożoność przestrzeni: O(V + E), ponieważ algorytm używa stosu do przechowywania bieżącej ścieżki i listy do przechowywania końcowego obwodu. Maksymalny rozmiar stosu może w najgorszym przypadku wynosić V + E, więc złożoność przestrzeni wynosi O (V + E).
Utwórz quiz
