Dado un grafo euleriano dirigido, imprima un circuito de Euler . El circuito de Euler es un camino que atraviesa cada borde de un gráfico y el camino termina en el vértice inicial. Ejemplos:
Input : Adjacency list for the below graph
Output : 0 -> 1 -> 2 -> 0
Input : Adjacency list for the below graph
Output : 0 -> 6 -> 4 -> 5 -> 0 -> 1
-> 2 -> 3 -> 4 -> 2 -> 0
Explanation:
In both the cases, we can trace the Euler circuit
by following the edges as indicated in the output.
Hemos discutido el problema de averiguar si un grafo dado es euleriano o no . En esta publicación, se analiza un algoritmo para imprimir el circuito o sendero euleriano. El mismo problema se puede resolver usando el Algoritmo de Fleury , sin embargo, su complejidad es O(E*E). Usando el Algoritmo de Hierholzer, podemos encontrar el circuito/camino en O(E), es decir, tiempo lineal. A continuación se muestra el algoritmo: ref ( wiki ). Recuerde que un grafo dirigido tiene un ciclo euleriano si se cumplen las siguientes condiciones (1) Todos los vértices con grados distintos de cero pertenecen a un solo componente fuertemente conectado. (2) El grado interior y exterior de cada vértice es el mismo. El algoritmo asume que el gráfico dado tiene un circuito euleriano.
- 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 de entrada y salida de cada vértice debe ser el mismo, cuando el camino entra en otro en el vértice w debe haber una arista no utilizada que deje w. El recorrido así formado es un recorrido cerrado, pero puede que no cubra todos los vértices y aristas del grafo inicial.
- Siempre que exista un vértice u que pertenezca al recorrido actual, pero que tenga aristas adyacentes que no formen parte del recorrido, se inicia otro camino desde u, siguiendo las aristas no utilizadas hasta volver a u, y se une al recorrido así formado hasta el recorrido anterior.
Por lo tanto, la idea es seguir siguiendo los bordes no utilizados y eliminándolos hasta que nos quedemos atascados. Una vez que nos atascamos, retrocedemos al vértice más cercano en nuestra ruta actual que tiene bordes sin usar, y repetimos el proceso hasta que se hayan usado todos los bordes. Podemos usar otro contenedor para mantener la ruta final. Tomemos un ejemplo:
Let the initial directed graph be as below
Let's start our path from 0.
Thus, curr_path = {0} and circuit = {}
Now let's use the edge 0->1
Now, curr_path = {0,1} and circuit = {}
similarly we reach up to 2 and then to 0 again as
Now, curr_path = {0,1,2} and circuit = {}
Then we go to 0, now since 0 haven't got any unused
edge we put 0 in circuit and back track till we find
an edge
We then have curr_path = {0,1,2} and circuit = {0}
Similarly, when we backtrack to 2, we don't find any
unused edge. Hence put 2 in the circuit and backtrack
again.
curr_path = {0,1} and circuit = {0,2}
After reaching 1 we go to through unused edge 1->3 and
then 3->4, 4->1 until all edges have been traversed.
The contents of the two containers look as:
curr_path = {0,1,3,4,1} and circuit = {0,2}
now as all edges have been used, the curr_path is
popped one by one into the circuit.
Finally, we've circuit = {0,2,1,4,3,1,0}
We print the circuit in reverse to obtain the path followed.
i.e., 0->1->3->4->1->1->2->0
A continuación se muestra la implementación del enfoque anterior:
C++
// A C++ program to print Eulerian circuit in given
// directed graph using Hierholzer algorithm
#include <bits/stdc++.h>
using namespace std;
void printCircuit(vector< vector<int> > adj)
{
// adj represents the adjacency list of
// the directed graph
// edge_count represents the number of edges
// emerging from a vertex
unordered_map<int,int> edge_count;
for (int i=0; i<adj.size(); i++)
{
//find the count of edges to keep track
//of unused edges
edge_count[i] = adj[i].size();
}
if (!adj.size())
return; //empty graph
// Maintain a stack to keep vertices
stack<int> curr_path;
// vector to store final circuit
vector<int> circuit;
// start from any vertex
curr_path.push(0);
int curr_v = 0; // Current vertex
while (!curr_path.empty())
{
// If there's remaining edge
if (edge_count[curr_v])
{
// Push the vertex
curr_path.push(curr_v);
// Find the next vertex using an edge
int next_v = adj[curr_v].back();
// and remove that edge
edge_count[curr_v]--;
adj[curr_v].pop_back();
// Move to next vertex
curr_v = next_v;
}
// back-track to find remaining circuit
else
{
circuit.push_back(curr_v);
// Back-tracking
curr_v = curr_path.top();
curr_path.pop();
}
}
// we've got the circuit, now print it in reverse
for (int i=circuit.size()-1; i>=0; i--)
{
cout << circuit[i];
if (i)
cout<<" -> ";
}
}
// Driver program to check the above function
int main()
{
vector< vector<int> > adj1, adj2;
// Input Graph 1
adj1.resize(3);
// Build the edges
adj1[0].push_back(1);
adj1[1].push_back(2);
adj1[2].push_back(0);
printCircuit(adj1);
cout << endl;
// Input Graph 2
adj2.resize(7);
adj2[0].push_back(1);
adj2[0].push_back(6);
adj2[1].push_back(2);
adj2[2].push_back(0);
adj2[2].push_back(3);
adj2[3].push_back(4);
adj2[4].push_back(2);
adj2[4].push_back(5);
adj2[5].push_back(0);
adj2[6].push_back(4);
printCircuit(adj2);
return 0;
}
Python3
# Python3 program to print Eulerian circuit in given
# directed graph using Hierholzer algorithm
def printCircuit(adj):
# adj represents the adjacency list of
# the directed graph
# edge_count represents the number of edges
# emerging from a vertex
edge_count = dict()
for i in range(len(adj)):
# find the count of edges to keep track
# of unused edges
edge_count[i] = len(adj[i])
if len(adj) == 0:
return # empty graph
# Maintain a stack to keep vertices
curr_path = []
# vector to store final circuit
circuit = []
# start from any vertex
curr_path.append(0)
curr_v = 0 # Current vertex
while len(curr_path):
# If there's remaining edge
if edge_count[curr_v]:
# Push the vertex
curr_path.append(curr_v)
# Find the next vertex using an edge
next_v = adj[curr_v][-1]
# and remove that edge
edge_count[curr_v] -= 1
adj[curr_v].pop()
# Move to next vertex
curr_v = next_v
# back-track to find remaining circuit
else:
circuit.append(curr_v)
# Back-tracking
curr_v = curr_path[-1]
curr_path.pop()
# we've got the circuit, now print it in reverse
for i in range(len(circuit) - 1, -1, -1):
print(circuit[i], end = "")
if i:
print(" -> ", end = "")
# Driver Code
if __name__ == "__main__":
# Input Graph 1
adj1 = [0] * 3
for i in range(3):
adj1[i] = []
# Build the edges
adj1[0].append(1)
adj1[1].append(2)
adj1[2].append(0)
printCircuit(adj1)
print()
# Input Graph 2
adj2 = [0] * 7
for i in range(7):
adj2[i] = []
adj2[0].append(1)
adj2[0].append(6)
adj2[1].append(2)
adj2[2].append(0)
adj2[2].append(3)
adj2[3].append(4)
adj2[4].append(2)
adj2[4].append(5)
adj2[5].append(0)
adj2[6].append(4)
printCircuit(adj2)
print()
# This code is contributed by
# sanjeev2552
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
Implementación alternativa: a continuación se muestran las mejoras realizadas a partir del código anterior
El código anterior mantuvo un conteo del número de aristas para cada vértice. Esto es innecesario ya que ya estamos manteniendo la lista de adyacencia. Simplemente eliminamos la creación de la array edge_count. En el algoritmo reemplazamos `if edge_count[current_v]` con `if adj[current_v]`
El código anterior empuja el Node inicial dos veces a la pila. Aunque la forma en que codificó el resultado es correcta, este enfoque es confuso e ineficiente. Eliminamos esto agregando el siguiente vértice a la pila, en lugar del actual.
En la parte principal, donde el autor prueba el algoritmo, la inicialización de las listas de adyacencia `adj1` y `adj2`fue un poco rara. Esa poción también está mejorada.
Python3
# Python3 program to print Eulerian circuit in given
# directed graph using Hierholzer algorithm
def printCircuit(adj):
# adj represents the adjacency list of
# the directed graph
if len(adj) == 0:
return # empty graph
# Maintain a stack to keep vertices
# We can start from any vertex, here we start with 0
curr_path = [0]
# list to store final circuit
circuit = []
while curr_path:
curr_v = curr_path[-1]
# If there's remaining edge in adjacency list
# of the current vertex
if adj[curr_v]:
# Find and remove the next vertex that is
# adjacent to the current vertex
next_v = adj[curr_v].pop()
# Push the new vertex to the stack
curr_path.append(next_v)
# back-track to find remaining circuit
else:
# Remove the current vertex and
# put it in the circuit
circuit.append(curr_path.pop())
# we've got the circuit, now print it in reverse
for i in range(len(circuit) - 1, -1, -1):
print(circuit[i], end = "")
if i:
print(" -> ", end = "")
# Driver Code
if __name__ == "__main__":
# Input Graph 1
adj1 = [[] for _ in range(3)]
# Build the edges
adj1[0].append(1)
adj1[1].append(2)
adj1[2].append(0)
printCircuit(adj1)
print()
# Input Graph 2
adj2 = [[] for _ in range(7)]
adj2[0].append(1)
adj2[0].append(6)
adj2[1].append(2)
adj2[2].append(0)
adj2[2].append(3)
adj2[3].append(4)
adj2[4].append(2)
adj2[4].append(5)
adj2[5].append(0)
adj2[6].append(4)
printCircuit(adj2)
print()
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
Complejidad temporal: O(V+E).
Este artículo es una contribución de Ashutosh Kumar . El artículo también contiene aportes de Nitish Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA