我已经实现了一种算法来为无向图中给定的起始顶点找到欧拉循环(使用 DFS 并删除已访问的边),但它总是只返回一条路径。如何修改算法以搜索顶点的所有可能欧拉循环?
相关代码如下:
typedef int Graph[200][200]; // adjacency matrix
int v, e; // vertex count, edge count
......
void DFS(Graph &G, int x) {
int i;
Push(x);
for (i = 0; i < v; i++)
if (G[i][x] > 0) {
G[i][x] = 0;
G[x][i] = 0;
DFS(G, i);
break;
}
最佳答案
在递归调用之后,您应该重新插入之前删除的边,并去掉断点。
void DFS(Graph &G, int x)
{
int i;
Push(x);
for (i = 0; i < v; i++)
if (G[i][x] > 0)
{
G[i][x] *= -1;
G[x][i] *= -1;
DFS(G, i);
G[i][x] *= -1;
G[x][i] *= -1;
}
}
您现在所需要的只是一种确定何时生成完整周期的方法,以便您可以打印它并继续进行下一个。当您消除了图表的每条边时,就会发生这种情况。
关于algorithm - 找到所有可能的欧拉循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6023137/