首页 文章

找到所有可能的欧拉循环

提问于
浏览
4

我已经实现了一个算法,在无向图中找到给定起始顶点的Euler循环(使用DFS并删除被访问的边),但它总是只返回一个路径 . 如何修改算法以搜索顶点的所有可能的Euler周期?

这是相关代码:

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

}

2 回答

  • 4

    在递归调用之后,您应该重新插入之前删除的边缘,并摆脱中断 .

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

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

  • -2

    你想循环遍历所有顶点 .

相关问题