使用每条边穿过每个节点的路径(柯尼斯堡的七座桥)
原文:https://www . geesforgeks . org/path-travel-nodes-use-edge seven-bridges-konigsberg/
这些节点之间有 n 个节点和 m 个桥。使用每条边打印通过每个节点的可能路径(如果可能),只通过每条边一次。
示例:
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"
它是图论中著名的问题之一,被称为“柯尼希斯堡七桥”问题。这个问题是由著名数学家莱昂哈德·欧拉在 1735 年解决的。这个问题也被认为是图论的开端。 当时的问题是:普鲁士的哥尼斯堡市周围有 7 座桥梁连接着 4 块土地。有没有什么方法可以从任何一片土地出发,穿过每一座桥一次,而且只穿过一次?请参见这些维基百科图片了解更多信息。
欧拉首先引入图论来解决这个问题。他认为每一个陆地都是一个图的节点,中间的每一座桥都是一条边。现在他计算了在那个图中是否有欧拉路径。如果有欧拉路径,那么就有解决方案,否则就没有。 这里的问题,是 1735 年问题的广义版本。
下面是实现:
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 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 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.
Output:
2-0 0-1 1-2 2-3
1-0 0-2 2-3 3-1 1-0 0-2
版权属于:月萌API www.moonapi.com,转载请注明出处