Yönlendirilmiş grafik için Hierholzer Algoritması
Yönlendirilmiş bir Eulerian grafiği verildiğinde görev, bir Euler devresi . Euler devresi, bir grafiğin her kenarını tam olarak bir kez geçen ve yol başlangıç tepe noktasında biten bir yoldur.
Not: Verilen grafik bir Euler devresi içermektedir.
Örnek:
Giriş: Yönlendirilmiş grafik
Çıkış: 0 3 4 0 2 1 0
Önkoşullar:
- tartıştık Belirli bir grafiğin Eulerian olup olmadığını bulma problemi Yönlendirilmemiş Grafik için
- Yönlendirilmiş Grpag'da Euler devresinin koşulları: (1) Tüm köşeler güçlü bağlı tek bir bileşene aittir. (2) Tüm köşelerin iç ve dış dereceleri aynıdır. Yönsüz bir grafik için durumun farklı olduğunu unutmayın (tüm köşelerin derecesi çifttir)
Yaklaşmak:
- Herhangi bir başlangıç köşesi v seçin ve bu köşeden v'ye dönene kadar kenarların izini takip edin. v dışında herhangi bir köşede sıkışıp kalmak mümkün değildir çünkü iz başka bir köşeye girdiğinde her köşenin iç ve dış derecesi aynı olmalıdır w'den ayrılan kullanılmayan bir kenar olmalıdır. Bu şekilde oluşturulan tur kapalı bir turdur ancak başlangıç grafiğinin tüm köşelerini ve kenarlarını kapsamayabilir.
- Geçerli tura ait olan ancak turun bir parçası olmayan bitişik kenarları olan bir u tepe noktası mevcut olduğu sürece, u'ya dönene kadar kullanılmayan kenarları takip ederek u'dan başka bir iz başlatır ve bu şekilde oluşturulan turu bir önceki turla birleştirir.
İllüstrasyon:
5 düğümlü yukarıdaki grafiğin örneğini ele alalım: adj = {{2 3} {0} {1} {4} {0}}.
- Tepe noktası 0'dan başla :
- Mevcut Yol: [0]
- Devre: []
- Tepe noktası 0 → 3 :
- Geçerli Yol: [0 3]
- Devre: []
- Köşe 3 → 4 :
- Geçerli Yol: [0 3 4]
- Devre: []
- Tepe noktası 4 → 0 :
- Geçerli Yol: [0 3 4 0]
- Devre: []
- Tepe noktası 0 → 2 :
- Geçerli Yol: [0 3 4 0 2]
- Devre: []
- Köşe 2 → 1 :
- Mevcut Yol: [0 3 4 0 2 1]
- Devre: []
- Tepe noktası 1 → 0 :
- Mevcut Yol: [0 3 4 0 2 1 0]
- Devre: []
- Köşe 0'a geri dönüş : Devreye 0 ekleyin.
- Mevcut Yol: [0 3 4 0 2 1]
- Devre: [0]
- Köşe 1'e geri dönüş : Devreye 1 ekleyin.
- Geçerli Yol: [0 3 4 0 2]
- Devre: [0 1]
- Köşe 2'ye geri dönüş : Devreye 2 ekleyin.
- Geçerli Yol: [0 3 4 0]
- Devre: [0 1 2]
- Köşe 0'a geri dönüş : Devreye 0 ekleyin.
- Geçerli Yol: [0 3 4]
- Devre: [0 1 2 0]
- Köşe 4'e geri dönüş : Devreye 4 ekleyin.
- Geçerli Yol: [0 3]
- Devre: [0 1 2 0 4]
- Köşe 3'e geri dönüş : Devreye 3 ekleyin.
- Mevcut Yol: [0]
- Devre: [0 1 2 0 4 3]
- Köşe 0'a geri dönüş : Devreye 0 ekleyin.
- Mevcut Yol: []
- Devre: [0 1 2 0 4 3 0]
Yukarıdaki yaklaşımın uygulaması aşağıdadır:
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 ' ' ); }
Çıkış
0 3 4 0 2 1 0
Zaman Karmaşıklığı: O(V + E) burada V, grafikteki köşelerin sayısı ve E, grafikteki kenarların sayısıdır. Bunun nedeni, algoritmanın derinlik öncelikli arama (DFS) yapması ve her köşeyi ve her kenarı tam olarak bir kez ziyaret etmesidir. Yani her köşe için onu ziyaret etmek O(1) zaman alır ve her kenar için onu geçmek O(1) zaman alır.
Alan karmaşıklığı: O(V + E), algoritma geçerli yolu depolamak için bir yığın ve son devreyi depolamak için bir liste kullandığından. Yığının maksimum boyutu en kötü ihtimalle V + E olabilir, dolayısıyla alan karmaşıklığı O(V + E) olur.
Test Oluştur
