Алгоритъмът на Hierholzer за ориентиран граф
При дадена насочена ойлерова графика задачата е да се отпечата верига на Ойлер . Веригата на Ойлер е път, който пресича всеки ръб на графика точно веднъж и пътят завършва в началния връх.
Забележка: Дадената графика съдържа верига на Ойлер.
Пример:
Вход: Насочена графа
Изход: 0 3 4 0 2 1 0
Предпоставки:
- Обсъждали сме проблем за намиране дали дадена графика е ойлерова или не за неориентиран граф
- Условия за Eulerian верига в Directed Grpag: (1) Всички върхове принадлежат на единичен силно свързан компонент. (2) Всички върхове имат еднаква входяща и изходяща степен. Обърнете внимание, че за неориентирана графа условието е различно (всички върхове имат четна степен)
Подход:
- Изберете който и да е начален връх v и следвайте следа от ръбове от този връх, докато се върнете към v. Не е възможно да останете в който и да е връх, различен от v, тъй като indegree и outdegree на всеки връх трябва да са еднакви, когато пътеката навлиза в друг връх w, трябва да има неизползван ръб, напускащ w. Обиколката, образувана по този начин, е затворена обиколка, но може да не покрива всички върхове и ръбове на първоначалния граф.
- Докато съществува връх u, който принадлежи на текущата обиколка, но има съседни ръбове, които не са част от обиколката, започнете друга следа от u, следваща неизползваните ръбове, докато се върнете към u и присъединете обиколката, образувана по този начин, към предишната обиколка.
Илюстрация:
Да вземем пример за горната графика с 5 възела: adj = {{2 3} {0} {1} {4} {0}}.
- Започнете от връх 0 :
- Текущ път: [0]
- Верига: []
- Връх 0 → 3 :
- Текущ път: [0 3]
- Верига: []
- Връх 3 → 4 :
- Текущ път: [0 3 4]
- Верига: []
- Връх 4 → 0 :
- Текущ път: [0 3 4 0]
- Верига: []
- Връх 0 → 2 :
- Текущ път: [0 3 4 0 2]
- Верига: []
- Връх 2 → 1 :
- Текущ път: [0 3 4 0 2 1]
- Верига: []
- Връх 1 → 0 :
- Текущ път: [0 3 4 0 2 1 0]
- Верига: []
- Обратно до връх 0 : Добавете 0 към веригата.
- Текущ път: [0 3 4 0 2 1]
- Верига: [0]
- Обратно до връх 1 : Добавете 1 към веригата.
- Текущ път: [0 3 4 0 2]
- Верига: [0 1]
- Обратно до връх 2 : Добавете 2 към веригата.
- Текущ път: [0 3 4 0]
- Верига: [0 1 2]
- Обратно до връх 0 : Добавете 0 към веригата.
- Текущ път: [0 3 4]
- Верига: [0 1 2 0]
- Връщане към връх 4 : Добавете 4 към веригата.
- Текущ път: [0 3]
- Верига: [0 1 2 0 4]
- Обратно до връх 3 : Добавете 3 към веригата.
- Текущ път: [0]
- Верига: [0 1 2 0 4 3]
- Обратно до връх 0 : Добавете 0 към веригата.
- Текущ път: []
- Верига: [0 1 2 0 4 3 0]
По-долу е изпълнението на горния подход:
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 ' ' ); }
Изход
0 3 4 0 2 1 0
Времева сложност: O(V + E), където V е броят на върховете, а E е броят на ръбовете в графиката. Причината за това е, че алгоритъмът извършва първо търсене в дълбочина (DFS) и посещава всеки връх и всеки ръб точно веднъж. Така че за всеки връх отнема O(1) време, за да го посети, а за всеки ръб отнема O(1) време, за да го обходи.
Сложност на пространството: O(V + E), тъй като алгоритъмът използва стек за съхраняване на текущия път и списък за съхраняване на крайната верига. Максималният размер на стека може да бъде V + E в най-лошия случай, така че пространствената сложност е O(V + E).
Създаване на тест
