Algoritmo de Hierholzer para grafo dirigido
Dado un gráfico euleriano dirigido, la tarea es imprimir un circuito de euler . Un circuito de Euler es un camino que atraviesa cada borde de un gráfico exactamente una vez y el camino termina en el vértice inicial.
Nota: El gráfico dado contiene un circuito de Euler.
Ejemplo:
Entrada: gráfico dirigido
Producción: 0 3 4 0 2 1 0
Requisitos previos:
- Hemos discutido el Problema de averiguar si una gráfica dada es euleriana o no. para un gráfico no dirigido
- Condiciones para el circuito euleriano en un grupo dirigido: (1) Todos los vértices pertenecen a un único componente fuertemente conectado. (2) Todos los vértices tienen el mismo grado de entrada y de salida. Tenga en cuenta que para un gráfico no dirigido la condición es diferente (todos los vértices tienen grados pares)
Acercarse:
- Elija cualquier vértice inicial v y siga un rastro de aristas desde ese vértice hasta regresar a v. No es posible quedarse atascado en ningún vértice que no sea v porque el grado interior y exterior de cada vértice debe ser el mismo cuando el camino ingresa a otro vértice w, debe haber un borde no utilizado que salga de w. El recorrido formado de esta manera es un recorrido cerrado pero puede que no cubra todos los vértices y aristas del gráfico inicial.
- Mientras exista un vértice u que pertenezca al recorrido actual pero que tenga aristas adyacentes que no formen parte del recorrido, iniciar otro recorrido desde u siguiendo aristas no utilizadas hasta regresar a u y unir el recorrido formado de esta manera al recorrido anterior.
Ilustración:
Tomando como ejemplo el gráfico anterior con 5 nodos: adj = {{2 3} {0} {1} {4} {0}}.
- Empezar en el vértice 0 :
- Ruta actual: [0]
- Circuito: []
- Vértice 0 → 3 :
- Ruta actual: [0 3]
- Circuito: []
- Vértice 3 → 4 :
- Ruta actual: [0 3 4]
- Circuito: []
- Vértice 4 → 0 :
- Ruta actual: [0 3 4 0]
- Circuito: []
- Vértice 0 → 2 :
- Ruta actual: [0 3 4 0 2]
- Circuito: []
- Vértice 2 → 1 :
- Ruta actual: [0 3 4 0 2 1]
- Circuito: []
- Vértice 1 → 0 :
- Ruta actual: [0 3 4 0 2 1 0]
- Circuito: []
- Retroceder hasta el vértice 0 : Agregue 0 al circuito.
- Ruta actual: [0 3 4 0 2 1]
- Circuito: [0]
- Retroceder hasta el vértice 1 : Suma 1 al circuito.
- Ruta actual: [0 3 4 0 2]
- Circuito: [0 1]
- Retroceder al vértice 2 : Suma 2 al circuito.
- Ruta actual: [0 3 4 0]
- Circuito: [0 1 2]
- Retroceder hasta el vértice 0 : Agregue 0 al circuito.
- Ruta actual: [0 3 4]
- Circuito: [0 1 2 0]
- Retroceder hasta el vértice 4 : Suma 4 al circuito.
- Ruta actual: [0 3]
- Circuito: [0 1 2 0 4]
- Retroceder hasta el vértice 3 : Suma 3 al circuito.
- Ruta actual: [0]
- Circuito: [0 1 2 0 4 3]
- Retroceder hasta el vértice 0 : Agregue 0 al circuito.
- Ruta actual: []
- Circuito: [0 1 2 0 4 3 0]
A continuación se muestra la implementación del enfoque anterior:
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 ' ' ); }
Producción
0 3 4 0 2 1 0
Complejidad del tiempo: O(V + E) donde V es el número de vértices y E es el número de aristas del gráfico. La razón de esto es que el algoritmo realiza una búsqueda en profundidad (DFS) y visita cada vértice y cada borde exactamente una vez. Entonces, para cada vértice se necesita O(1) tiempo para visitarlo y para cada arista se necesita O(1) tiempo para atravesarlo.
Complejidad del espacio: O(V + E) ya que el algoritmo utiliza una pila para almacenar la ruta actual y una lista para almacenar el circuito final. El tamaño máximo de la pila puede ser V + E en el peor de los casos, por lo que la complejidad del espacio es O (V + E).
Crear cuestionario
