Find all possible Euler cycles

问题:

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?

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

}

回答1:

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.

回答2:

You want to loop through all vertex.