Dada una representación matricial de adyacencia de un grafo no dirigido. Encuentra si hay algún Camino Euleriano en el gráfico. Si no hay ruta, imprima «Sin solución». Si hay alguna ruta, imprima la ruta.
Ejemplos:
Input : [[0, 1, 0, 0, 1],
[1, 0, 1, 1, 0],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 0],
[1, 0, 0, 0, 0]]
Output : 5 -> 1 -> 2 -> 4 -> 3 -> 2
Input : [[0, 1, 0, 1, 1],
[1, 0, 1, 0, 1],
[0, 1, 0, 1, 1],
[1, 1, 1, 0, 0],
[1, 0, 1, 0, 0]]
Output : "No Solution"
El caso base de este problema es que si el número de vértices con un número impar de aristas (es decir, grado impar) es mayor que 2, entonces no hay un camino euleriano.
Si tiene la solución y todos los Nodes tienen un número par de aristas entonces podemos iniciar nuestro camino desde cualquiera de los Nodes.
Si tiene la solución y exactamente dos vértices tienen un número impar de aristas entonces tenemos que empezar nuestro camino desde uno de estos dos vértices.
No se dará el caso de que exactamente un vértice tenga un número impar de aristas, ya que hay un número par de aristas en total.
Proceso para encontrar el camino:
- Primero, toma una pila vacía y un camino vacío.
- Si todos los vértices tienen un número par de aristas, comience desde cualquiera de ellos. Si dos de los vértices tienen un número impar de aristas, comienza desde uno de ellos. Establezca la corriente variable en este vértice inicial.
- Si el vértice actual tiene al menos un Node adyacente, primero descubra ese Node y luego descubra el Node actual retrocediendo. Para hacerlo, agregue el Node actual a la pila, elimine el borde entre el Node actual y el Node vecino, establezca actual en el Node vecino.
- Si el Node actual no tiene ningún vecino, agréguelo a la ruta y coloque la pila actual en el vértice emergente.
- Repita los procesos 3 y 4 hasta que la pila esté vacía y el Node actual no tenga ningún vecino.
Después de la variable de la ruta del proceso, se encuentra la ruta Euleriana.
C++
// Efficient C++ program to
// find out Eulerian path
#include <bits/stdc++.h>
using namespace std;
// Function to find out the path
// It takes the adjacency matrix
// representation of the graph as input
void findpath(int graph[][5], int n)
{
vector<int> numofadj;
// Find out number of edges each vertex has
for (int i = 0; i < n; i++)
numofadj.push_back(accumulate(graph[i],
graph[i] + 5, 0));
// Find out how many vertex has odd number edges
int startpoint = 0, numofodd = 0;
for (int i = n - 1; i >= 0; i--)
{
if (numofadj[i] % 2 == 1)
{
numofodd++;
startpoint = i;
}
}
// If number of vertex with odd number of edges
// is greater than two return "No Solution".
if (numofodd > 2)
{
cout << "No Solution" << endl;
return;
}
// If there is a path find the path
// Initialize empty stack and path
// take the starting current as discussed
stack<int> stack;
vector<int> path;
int cur = startpoint;
// Loop will run until there is element in the stack
// or current edge has some neighbour.
while (!stack.empty() or
accumulate(graph[cur],
graph[cur] + 5, 0) != 0)
{
// If current node has not any neighbour
// add it to path and pop stack
// set new current to the popped element
if (accumulate(graph[cur],
graph[cur] + 5, 0) == 0)
{
path.push_back(cur);
cur = stack.top();
stack.pop();
}
// If the current vertex has at least one
// neighbour add the current vertex to stack,
// remove the edge between them and set the
// current to its neighbour.
else
{
for (int i = 0; i < n; i++)
{
if (graph[cur][i] == 1)
{
stack.push(cur);
graph[cur][i] = 0;
graph[i][cur] = 0;
cur = i;
break;
}
}
}
}
// print the path
for (auto ele : path) cout << ele << " -> ";
cout << cur << endl;
}
// Driver Code
int main()
{
// Test case 1
int graph1[][5] = {{0, 1, 0, 0, 1},
{1, 0, 1, 1, 0},
{0, 1, 0, 1, 0},
{0, 1, 1, 0, 0},
{1, 0, 0, 0, 0}};
int n = sizeof(graph1) / sizeof(graph1[0]);
findpath(graph1, n);
// Test case 2
int graph2[][5] = {{0, 1, 0, 1, 1},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 1},
{1, 1, 1, 0, 0},
{1, 0, 1, 0, 0}};
n = sizeof(graph1) / sizeof(graph1[0]);
findpath(graph2, n);
// Test case 3
int graph3[][5] = {{0, 1, 0, 0, 1},
{1, 0, 1, 1, 1},
{0, 1, 0, 1, 0},
{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0}};
n = sizeof(graph1) / sizeof(graph1[0]);
findpath(graph3, n);
}
// This code is contributed by
// sanjeev2552
Java
// Efficient Java program to
// find out Eulerian path
import java.util.*;
class GFG
{
// Function to find out the path
// It takes the adjacency matrix
// representation of the graph as input
static void findpath(int[][] graph, int n)
{
Vector<Integer> numofadj = new Vector<>();
// Find out number of edges each vertex has
for (int i = 0; i < n; i++)
numofadj.add(accumulate(graph[i], 0));
// Find out how many vertex has odd number edges
int startPoint = 0, numofodd = 0;
for (int i = n - 1; i >= 0; i--)
{
if (numofadj.elementAt(i) % 2 == 1)
{
numofodd++;
startPoint = i;
}
}
// If number of vertex with odd number of edges
// is greater than two return "No Solution".
if (numofodd > 2)
{
System.out.println("No Solution");
return;
}
// If there is a path find the path
// Initialize empty stack and path
// take the starting current as discussed
Stack<Integer> stack = new Stack<>();
Vector<Integer> path = new Vector<>();
int cur = startPoint;
// Loop will run until there is element in the stack
// or current edge has some neighbour.
while (!stack.isEmpty() || accumulate(graph[cur], 0) != 0)
{
// If current node has not any neighbour
// add it to path and pop stack
// set new current to the popped element
if (accumulate(graph[cur], 0) == 0)
{
path.add(cur);
cur = stack.pop();
// If the current vertex has at least one
// neighbour add the current vertex to stack,
// remove the edge between them and set the
// current to its neighbour.
}
else
{
for (int i = 0; i < n; i++)
{
if (graph[cur][i] == 1)
{
stack.add(cur);
graph[cur][i] = 0;
graph[i][cur] = 0;
cur = i;
break;
}
}
}
}
// print the path
for (int ele : path)
System.out.print(ele + " -> ");
System.out.println(cur);
}
static int accumulate(int[] arr, int sum)
{
for (int i : arr)
sum += i;
return sum;
}
// Driver Code
public static void main(String[] args)
{
// Test case 1
int[][] graph1 = { { 0, 1, 0, 0, 1 },
{ 1, 0, 1, 1, 0 },
{ 0, 1, 0, 1, 0 },
{ 0, 1, 1, 0, 0 },
{ 1, 0, 0, 0, 0 } };
int n = graph1.length;
findpath(graph1, n);
// Test case 2
int[][] graph2 = { { 0, 1, 0, 1, 1 },
{ 1, 0, 1, 0, 1 },
{ 0, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 0 },
{ 1, 0, 1, 0, 0 } };
n = graph2.length;
findpath(graph2, n);
// Test case 3
int[][] graph3 = { { 0, 1, 0, 0, 1 },
{ 1, 0, 1, 1, 1 },
{ 0, 1, 0, 1, 0 },
{ 0, 1, 1, 0, 1 },
{ 1, 1, 0, 1, 0 } };
n = graph3.length;
findpath(graph3, n);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Efficient Python3 program to
# find out Eulerian path
# Function to find out the path
# It takes the adjacency matrix
# representation of the graph as input
def findpath(graph, n):
numofadj = []
# Find out number of edges each
# vertex has
for i in range(n):
numofadj.append(sum(graph[i]))
# Find out how many vertex has
# odd number edges
startpoint, numofodd = 0, 0
for i in range(n - 1, -1, -1):
if (numofadj[i] % 2 == 1):
numofodd += 1
startpoint = i
# If number of vertex with odd number of edges
# is greater than two return "No Solution".
if (numofodd > 2):
print("No Solution")
return
# If there is a path find the path
# Initialize empty stack and path
# take the starting current as discussed
stack = []
path = []
cur = startpoint
# Loop will run until there is element in the
# stack or current edge has some neighbour.
while (len(stack) > 0 or sum(graph[cur])!= 0):
# If current node has not any neighbour
# add it to path and pop stack set new
# current to the popped element
if (sum(graph[cur]) == 0):
path.append(cur)
cur = stack[-1]
del stack[-1]
# If the current vertex has at least one
# neighbour add the current vertex to stack,
# remove the edge between them and set the
# current to its neighbour.
else:
for i in range(n):
if (graph[cur][i] == 1):
stack.append(cur)
graph[cur][i] = 0
graph[i][cur] = 0
cur = i
break
# Print the path
for ele in path:
print(ele, end = " -> ")
print(cur)
# Driver Code
if __name__ == '__main__':
# Test case 1
graph1 = [ [ 0, 1, 0, 0, 1 ],
[ 1, 0, 1, 1, 0 ],
[ 0, 1, 0, 1, 0 ],
[ 0, 1, 1, 0, 0 ],
[ 1, 0, 0, 0, 0 ] ]
n = len(graph1)
findpath(graph1, n)
# Test case 2
graph2 = [ [ 0, 1, 0, 1, 1 ],
[ 1, 0, 1, 0, 1 ],
[ 0, 1, 0, 1, 1 ],
[ 1, 1, 1, 0, 0 ],
[ 1, 0, 1, 0, 0 ] ]
n = len(graph2)
findpath(graph2, n)
# Test case 3
graph3 = [ [ 0, 1, 0, 0, 1 ],
[ 1, 0, 1, 1, 1 ],
[ 0, 1, 0, 1, 0 ],
[ 0, 1, 1, 0, 1 ],
[ 1, 1, 0, 1, 0 ] ]
n = len(graph3)
findpath(graph3, n)
# This code is contributed by mohit kumar 29
C#
// Efficient C# program to
// find out Eulerian path
using System;
using System.Collections.Generic;
class GFG{
// Function to find out the path
// It takes the adjacency matrix
// representation of the graph
// as input
static void findpath(int[,] graph,
int n)
{
List<int> numofadj =
new List<int>();
// Find out number of edges
// each vertex has
for (int i = 0; i < n; i++)
numofadj.Add(accumulate(graph,
i, 0));
// Find out how many vertex has
// odd number edges
int startPoint = 0, numofodd = 0;
for (int i = n - 1; i >= 0; i--)
{
if (numofadj[i] % 2 == 1)
{
numofodd++;
startPoint = i;
}
}
// If number of vertex with odd
// number of edges is greater than
// two return "No Solution".
if (numofodd > 2)
{
Console.WriteLine("No Solution");
return;
}
// If there is a path find the path
// Initialize empty stack and path
// take the starting current as
// discussed
Stack<int> stack = new Stack<int>();
List<int> path = new List<int>();
int cur = startPoint;
// Loop will run until there is element
// in the stack or current edge has some
// neighbour.
while (stack.Count != 0 ||
accumulate(graph, cur, 0) != 0)
{
// If current node has not any
// neighbour add it to path and
// pop stack set new current to
// the popped element
if (accumulate(graph,cur, 0) == 0)
{
path.Add(cur);
cur = stack.Pop();
// If the current vertex has at
// least one neighbour add the
// current vertex to stack, remove
// the edge between them and set the
// current to its neighbour.
}
else
{
for (int i = 0; i < n; i++)
{
if (graph[cur, i] == 1)
{
stack.Push(cur);
graph[cur, i] = 0;
graph[i, cur] = 0;
cur = i;
break;
}
}
}
}
// print the path
foreach (int ele in path)
Console.Write(ele + " -> ");
Console.WriteLine(cur);
}
static int accumulate(int[,] matrix,
int row, int sum)
{
int []arr = GetRow(matrix,
row);
foreach (int i in arr)
sum += i;
return sum;
}
public static int[] GetRow(int[,] matrix,
int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver Code
public static void Main(String[] args)
{
// Test case 1
int[,] graph1 = {{0, 1, 0, 0, 1},
{1, 0, 1, 1, 0},
{0, 1, 0, 1, 0},
{0, 1, 1, 0, 0},
{1, 0, 0, 0, 0}};
int n = graph1.GetLength(0);
findpath(graph1, n);
// Test case 2
int[,] graph2 = {{0, 1, 0, 1, 1},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 1},
{1, 1, 1, 0, 0},
{1, 0, 1, 0, 0}};
n = graph2.GetLength(0);
findpath(graph2, n);
// Test case 3
int[,] graph3 = {{0, 1, 0, 0, 1},
{1, 0, 1, 1, 1},
{0, 1, 0, 1, 0},
{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0}};
n = graph3.GetLength(0);
findpath(graph3, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Efficient JavaScript program to
// find out Eulerian path
// Function to find out the path
// It takes the adjacency matrix
// representation of the graph as input
function sum(a){
let Sum = 0
for(let x of a)
Sum += x
return Sum
}
function findpath(graph, n){
let numofadj = []
// Find out number of edges each
// vertex has
for(let i=0;i<n;i++)
numofadj.push(sum(graph[i]))
// Find out how many vertex has
// odd number edges
let startpoint = 0, numofodd = 0
for(let i=n-1;i>=0;i--){
if (numofadj[i] % 2 == 1){
numofodd += 1
startpoint = i
}
}
// If number of vertex with odd number of edges
// is greater than two return "No Solution".
if (numofodd > 2){
document.write("No Solution","</br>")
return
}
// If there is a path find the path
// Initialize empty stack and path
// take the starting current as discussed
let stack = []
let path = []
let cur = startpoint
// Loop will run until there is element in the
// stack or current edge has some neighbour.
while (stack.length > 0 || sum(graph[cur])!= 0){
// If current node has not any neighbour
// add it to path and pop stack set new
// current to the popped element
if (sum(graph[cur]) == 0){
path.push(cur)
cur = stack.pop()
}
// If the current vertex has at least one
// neighbour add the current vertex to stack,
// remove the edge between them and set the
// current to its neighbour.
else{
for(let i=0;i<n;i++){
if (graph[cur][i] == 1){
stack.push(cur)
graph[cur][i] = 0
graph[i][cur] = 0
cur = i
break
}
}
}
}
// Print the path
for(let ele of path)
document.write(ele," -> ")
document.write(cur,"</br>")
}
// Driver Code
// Test case 1
let graph1 = [ [ 0, 1, 0, 0, 1 ],
[ 1, 0, 1, 1, 0 ],
[ 0, 1, 0, 1, 0 ],
[ 0, 1, 1, 0, 0 ],
[ 1, 0, 0, 0, 0 ] ]
let n = graph1.length
findpath(graph1, n)
// Test case 2
let graph2 = [ [ 0, 1, 0, 1, 1 ],
[ 1, 0, 1, 0, 1 ],
[ 0, 1, 0, 1, 1 ],
[ 1, 1, 1, 0, 0 ],
[ 1, 0, 1, 0, 0 ] ]
n = graph2.length
findpath(graph2, n)
// Test case 3
let graph3 = [ [ 0, 1, 0, 0, 1 ],
[ 1, 0, 1, 1, 1 ],
[ 0, 1, 0, 1, 0 ],
[ 0, 1, 1, 0, 1 ],
[ 1, 1, 0, 1, 0 ] ]
n = graph3.length
findpath(graph3, n)
// This code is contributed by shinjanpatra
</script>
Producción:
4 -> 0 -> 1 -> 3 -> 2 -> 1 No Solution 4 -> 3 -> 2 -> 1 -> 4 -> 0 -> 1 -> 3
Complejidad de tiempo:
La complejidad de tiempo de ejecución de este algoritmo es O(E). Este algoritmo también se puede utilizar para encontrar el circuito euleriano. Si el primer y el último vértice del camino son iguales, entonces será un circuito euleriano.