Hay n Nodes y m puentes entre estos Nodes. Imprima la ruta posible a través de cada Node usando cada borde (si es posible), viajando a través de cada borde solo una vez.
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"
Es uno de los problemas más famosos de la Teoría de Grafos y conocido como problema de los “Siete Puentes de Königsberg”. Este problema fue resuelto por el famoso matemático Leonhard Euler en 1735. Este problema también se considera como el comienzo de la teoría de grafos.
El problema en ese entonces era que: había 7 puentes que conectaban 4 tierras alrededor de la ciudad de Königsberg en Prusia. ¿Había alguna forma de empezar desde cualquiera de los terrenos y pasar por cada uno de los puentes una vez y solo una vez? Consulte estas imágenes de wikipedia para obtener más claridad.
Euler introdujo por primera vez la teoría de grafos para resolver este problema. Consideró cada una de las tierras como un Node de un gráfico y cada puente en el medio como un borde en el medio. Ahora calculó si hay algún Camino Euleriano en ese gráfico. Si hay un camino euleriano, entonces hay una solución; de lo contrario, no.
Problema aquí, es una versión generalizada del problema en 1735.
A continuación se muestra la implementación:
C++
// A C++ program print Eulerian Trail in a
// given Eulerian or Semi-Eulerian Graph
#include <iostream>
#include <string.h>
#include <algorithm>
#include <list>
using namespace std;
// A class that represents an undirected graph
class Graph
{
// No. of vertices
int V;
// A dynamic array of adjacency lists
list<int> *adj;
public:
// Constructor and destructor
Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
~Graph()
{
delete [] adj;
}
// functions to add and remove edge
void addEdge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void rmvEdge(int u, int v);
// Methods to print Eulerian tour
void printEulerTour();
void printEulerUtil(int s);
// This function returns count of vertices
// reachable from v. It does DFS
int DFSCount(int v, bool visited[]);
// Utility function to check if edge u-v
// is a valid next edge in Eulerian trail or circuit
bool isValidNextEdge(int u, int v);
};
/* The main function that print Eulerian Trail.
It first finds an odd degree vertex (if there is any)
and then calls printEulerUtil() to print the path */
void Graph::printEulerTour()
{
// Find a vertex with odd degree
int u = 0;
for (int i = 0; i < V; i++)
if (adj[i].size() & 1)
{
u = i;
break;
}
// Print tour starting from oddv
printEulerUtil(u);
cout << endl;
}
// Print Euler tour starting from vertex u
void Graph::printEulerUtil(int u)
{
// Recur for all the vertices adjacent to
// this vertex
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
int v = *i;
// If edge u-v is not removed and it's a
// valid next edge
if (v != -1 && isValidNextEdge(u, v))
{
cout << u << "-" << v << " ";
rmvEdge(u, v);
printEulerUtil(v);
}
}
}
// The function to check if edge u-v can be considered
// as next edge in Euler Tout
bool Graph::isValidNextEdge(int u, int v)
{
// The edge u-v is valid in one of the following
// two cases:
// 1) If v is the only adjacent vertex of u
int count = 0; // To store count of adjacent vertices
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (*i != -1)
count++;
if (count == 1)
return true;
// 2) If there are multiple adjacents, then u-v
// is not a bridge
// Do following steps to check if u-v is a bridge
// 2.a) count of vertices reachable from u
bool visited[V];
memset(visited, false, V);
int count1 = DFSCount(u, visited);
// 2.b) Remove edge (u, v) and after removing
// the edge, count vertices reachable from u
rmvEdge(u, v);
memset(visited, false, V);
int count2 = DFSCount(u, visited);
// 2.c) Add the edge back to the graph
addEdge(u, v);
// 2.d) If count1 is greater, then edge (u, v)
// is a bridge
return (count1 > count2)? false: true;
}
// This function removes edge u-v from graph.
// It removes the edge by replacing adjacent
// vertex value with -1.
void Graph::rmvEdge(int u, int v)
{
// Find v in adjacency list of u and replace
// it with -1
list<int>::iterator iv = find(adj[u].begin(),
adj[u].end(), v);
*iv = -1;
// Find u in adjacency list of v and replace
// it with -1
list<int>::iterator iu = find(adj[v].begin(),
adj[v].end(), u);
*iu = -1;
}
// A DFS based function to count reachable
// vertices from v
int Graph::DFSCount(int v, bool visited[])
{
// Mark the current node as visited
visited[v] = true;
int count = 1;
// Recur for all vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (*i != -1 && !visited[*i])
count += DFSCount(*i, visited);
return count;
}
// Driver program to test above function
int main()
{
// Let us first create and test
// graphs shown in above figure
Graph g1(4);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.printEulerTour();
Graph g3(4);
g3.addEdge(0, 1);
g3.addEdge(1, 0);
g3.addEdge(0, 2);
g3.addEdge(2, 0);
g3.addEdge(2, 3);
g3.addEdge(3, 1);
// comment out this line and you will see that
// it gives TLE because there is no possible
// output g3.addEdge(0, 3);
g3.printEulerTour();
return 0;
}
Java
// A java program print Eulerian Trail in a
// given Eulerian or Semi-Eulerian Graph
import java.util.*;
public class GFG{
// A class that represents an undirected graph
static class Graph
{
// No. of vertices
int V;
// A dynamic array of adjacency lists
ArrayList<ArrayList<Integer>> adj;
// Constructor
Graph(int V)
{
this.V = V;
adj = new ArrayList<ArrayList<Integer>>();
for(int i=0; i<V; i++){
adj.add(new ArrayList<Integer>());
}
}
// functions to add and remove edge
void addEdge(int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// This function removes edge u-v from graph.
// It removes the edge by replacing adjacent
// vertex value with -1.
void rmvEdge(int u, int v)
{
// Find v in adjacency list of u and replace
// it with -1
int iv = find(adj.get(u), v);
adj.get(u).set(iv, -1);
// Find u in adjacency list of v and replace
// it with -1
int iu = find(adj.get(v), u);
adj.get(v).set(iu, -1);
}
int find(ArrayList<Integer> al, int v){
for(int i=0; i<al.size(); i++){
if(al.get(i) == v){
return i;
}
}
return -1;
}
// Methods to print Eulerian tour
/* The main function that print Eulerian Trail.
It first finds an odd degree vertex (if there is any)
and then calls printEulerUtil() to print the path */
void printEulerTour()
{
// Find a vertex with odd degree
int u = 0;
for (int i = 0; i < V; i++){
if (adj.get(i).size() % 2 == 1)
{
u = i;
break;
}
}
// Print tour starting from oddv
printEulerUtil(u);
System.out.println();
}
// Print Euler tour starting from vertex u
void printEulerUtil(int u)
{
// Recur for all the vertices adjacent to
// this vertex
for (int i = 0; i<adj.get(u).size(); ++i)
{
int v = adj.get(u).get(i);
// If edge u-v is not removed and it's a
// valid next edge
if (v != -1 && isValidNextEdge(u, v))
{
System.out.print(u + "-" + v + " ");
rmvEdge(u, v);
printEulerUtil(v);
}
}
}
// This function returns count of vertices
// reachable from v. It does DFS
// A DFS based function to count reachable
// vertices from v
int DFSCount(int v, boolean visited[])
{
// Mark the current node as visited
visited[v] = true;
int count = 1;
// Recur for all vertices adjacent to this vertex
for (int i = 0; i<adj.get(v).size(); ++i){
int u = adj.get(v).get(i);
if (u != -1 && !visited[u]){
count += DFSCount(u, visited);
}
}
return count;
}
// Utility function to check if edge u-v
// is a valid next edge in Eulerian trail or circuit
// The function to check if edge u-v can be considered
// as next edge in Euler Tout
boolean isValidNextEdge(int u, int v)
{
// The edge u-v is valid in one of the following
// two cases:
// 1) If v is the only adjacent vertex of u
int count = 0; // To store count of adjacent vertices
for (int i = 0; i<adj.get(u).size(); ++i)
if (adj.get(u).get(i) != -1)
count++;
if (count == 1)
return true;
// 2) If there are multiple adjacents, then u-v
// is not a bridge
// Do following steps to check if u-v is a bridge
// 2.a) count of vertices reachable from u
boolean visited[] = new boolean[V];
Arrays.fill(visited, false);
int count1 = DFSCount(u, visited);
// 2.b) Remove edge (u, v) and after removing
// the edge, count vertices reachable from u
rmvEdge(u, v);
Arrays.fill(visited, false);
int count2 = DFSCount(u, visited);
// 2.c) Add the edge back to the graph
addEdge(u, v);
// 2.d) If count1 is greater, then edge (u, v)
// is a bridge
return (count1 > count2)? false: true;
}
}
// Driver program to test above function
public static void main(String args[])
{
// Let us first create and test
// graphs shown in above figure
Graph g1 = new Graph(4);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.printEulerTour();
Graph g3 = new Graph(4);
g3.addEdge(0, 1);
g3.addEdge(1, 0);
g3.addEdge(0, 2);
g3.addEdge(2, 0);
g3.addEdge(2, 3);
g3.addEdge(3, 1);
// comment out this line and you will see that
// it gives TLE because there is no possible
// output g3.addEdge(0, 3);
g3.printEulerTour();
}
}
// This code is contributed by adityapande88.
Producción:
2-0 0-1 1-2 2-3 1-0 0-2 2-3 3-1 1-0 0-2