查找所有可能的欧拉周期 [英] Find all possible Euler cycles

问题描述

我已经实现了一个算法来找到一个欧拉循环对于给定的起始顶点（使用DFS和移除参观边）无向图，但它总是返回只有一条路径。如何修改该算法来搜索所有可能的欧拉周期为一个顶点？

I have implemented an algorithm to find an Euler cycle for a given starting vertex in an undirected graph (using DFS and removing visited edges), but it always returns only one path. How do I modify the algorithm to search for all possible Euler cycles for a vertex?

下面是相关的code：

Here is relevant code:

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

}

推荐答案

递归调用后，你应该重新插入你以前删除的边，并摆脱了破发。

After the recursive call, you should reinsert the edges you deleted before, and get rid of the 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;
        }

}

你现在需要的是一种方法来找出当你生成一个完整的周期，因此您可以打印出来并移动到下一个。这发生在你已经消除了你的图的每个边缘。

All you need now is a way to figure out when you've generated a full cycle so you can print it and move on to the next. That happens when you've eliminated every edge of your graph.

这篇关于查找所有可能的欧拉周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！