找出所有可能的欧拉循环

Question

我已经实现了一种算法，用于在无向图中查找给定起始顶点的欧拉循环（使用 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;
    }

}

Answer 1

递归调用后，您应该重新插入之前删除的边，并消除中断。

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;
        }

}

现在您所需要的只是一种方法来确定何时生成了完整的循环，以便您可以打印它并继续进行下一个循环。当你消除了图表的每条边时就会发生这种情况。