Алгоритм Ієргольцера для орієнтованого графа
Для орієнтованого ейлерового графа завдання полягає в тому, щоб надрукувати Схема Ейлера . Схема Ейлера — це шлях, який проходить кожне ребро графа рівно один раз і закінчується на початковій вершині.
Примітка: Даний граф містить схему Ейлера.
приклад:
Вхід: орієнтований граф
Вихід: 0 3 4 0 2 1 0
Передумови:
- Ми обговорили завдання з'ясувати, чи є даний граф ейлеровим чи ні для неорієнтованого графа
- Умови для ейлерового контуру в орієнтованому групі: (1) Усі вершини належать одній сильно зв’язній компоненті. (2) Усі вершини мають однаковий внутрішній і зовнішній ступінь. Зверніть увагу, що для неорієнтованого графа умова інша (усі вершини мають парний ступінь)
Підхід:
- Виберіть будь-яку початкову вершину v і дотримуйтеся сліду ребер від цієї вершини до повернення до v. Неможливо застрягти на будь-якій вершині, окрім v, тому що вхідний і відступний ступінь кожної вершини мають бути однаковими, коли слід входить в іншу вершину 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).
Створіть вікторину
