Hierholzerio algoritmas nukreiptam grafikui
Atsižvelgiant į nukreiptą Eulerio grafiką, užduotis yra atspausdinti an Eilerio grandinė . Eulerio grandinė yra kelias, kuris tiksliai vieną kartą kerta kiekvieną grafiko kraštą ir kelias baigiasi pradinėje viršūnėje.
Pastaba: Pateiktame grafike yra Eulerio grandinė.
Pavyzdys:
Įvestis: nukreiptas grafikas
Išvestis: 0 3 4 0 2 1 0
Būtinos sąlygos:
- Mes aptarėme Problema išsiaiškinti, ar tam tikras grafikas yra Eulerio, ar ne neorientuotam grafikui
- Sąlygos Eulerio grandinei nukreiptoje grpagoje: (1) Visos viršūnės priklauso vienam stipriai sujungtam komponentui. (2) Visos viršūnės turi tą patį laipsnį ir išorinį laipsnį. Atkreipkite dėmesį, kad nenukreipto grafo sąlyga yra kitokia (visos viršūnės turi lygų laipsnį)
Prieiga:
- Pasirinkite bet kurią pradinę viršūnę v ir sekite briaunų pėdsaką nuo tos viršūnės iki grįžimo į v. Neįmanoma įstrigti bet kurioje kitoje viršūnėje, išskyrus v, nes kiekvienos viršūnės laipsnis ir išorinis laipsnis turi būti vienodi, kai takas patenka į kitą viršūnę w, turi būti nepanaudota briauna, paliekanti w. Taip suformuotas turas yra uždaras, bet gali neapimti visų pradinio grafiko viršūnių ir kraštų.
- Kol yra viršūnė u, kuri priklauso dabartiniam turui, bet turi gretimus kraštus, kurie nėra kelionės dalis, pradėkite kitą taką nuo u eidami nenaudojamomis briaunomis iki grįžimo į u ir taip suformuotą turą prijunkite prie ankstesnės kelionės.
Iliustracija:
Atsižvelgiant į aukščiau pateiktą grafiką su 5 mazgais: adj = {{2 3} {0} {1} {4} {0}}.
- Pradėkite nuo viršūnės 0 :
- Dabartinis kelias: [0]
- Grandinė: []
- Viršūnė 0 → 3 :
- Dabartinis kelias: [0 3]
- Grandinė: []
- Viršūnė 3 → 4 :
- Dabartinis kelias: [0 3 4]
- Grandinė: []
- Viršūnė 4 → 0 :
- Dabartinis kelias: [0 3 4 0]
- Grandinė: []
- Viršūnė 0 → 2 :
- Dabartinis kelias: [0 3 4 0 2]
- Grandinė: []
- Viršūnė 2 → 1 :
- Dabartinis kelias: [0 3 4 0 2 1]
- Grandinė: []
- Viršūnė 1 → 0 :
- Dabartinis kelias: [0 3 4 0 2 1 0]
- Grandinė: []
- Grįžti į viršūnę 0 : pridėti 0 į grandinę.
- Dabartinis kelias: [0 3 4 0 2 1]
- Grandinė: [0]
- Grįžti į 1 viršūnę : pridėkite 1 prie grandinės.
- Dabartinis kelias: [0 3 4 0 2]
- Grandinė: [0 1]
- Grįžti į 2 viršūnę : pridėkite 2 prie grandinės.
- Dabartinis kelias: [0 3 4 0]
- Grandinė: [0 1 2]
- Grįžti į viršūnę 0 : pridėti 0 į grandinę.
- Dabartinis kelias: [0 3 4]
- Grandinė: [0 1 2 0]
- Grįžti į 4 viršūnę : pridėkite 4 prie grandinės.
- Dabartinis kelias: [0 3]
- Grandinė: [0 1 2 0 4]
- Grįžti į 3 viršūnę : pridėkite 3 prie grandinės.
- Dabartinis kelias: [0]
- Grandinė: [0 1 2 0 4 3]
- Grįžti į viršūnę 0 : pridėti 0 į grandinę.
- Dabartinis kelias: []
- Grandinė: [0 1 2 0 4 3 0]
Toliau pateikiamas pirmiau nurodyto metodo įgyvendinimas:
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 ' ' ); }
Išvestis
0 3 4 0 2 1 0
Laiko sudėtingumas: O(V + E) čia V – viršūnių skaičius, o E – kraštinių skaičius grafe. Taip yra todėl, kad algoritmas atlieka giluminę paiešką (DFS) ir kiekvieną viršūnę bei kiekvieną kraštą aplanko tiksliai vieną kartą. Taigi kiekvienai viršūnei reikia O(1) laiko ją aplankyti, o kiekvienai briaunai reikia O(1) laiko ją įveikti.
Erdvės sudėtingumas: O (V + E), kaip algoritmas, naudoja krūvą, kad išsaugotų dabartinį kelią, ir sąrašą, kad išsaugotų galutinę grandinę. Didžiausias krūvos dydis blogiausiu atveju gali būti V + E, todėl erdvės sudėtingumas yra O(V + E).
Sukurti viktoriną
