Найти все возможные циклы Эйлера

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

}

Все, что вам сейчас нужно, это способ выяснить, когда вы сгенерировали полный цикл, чтобы вы могли распечатать его и перейти к следующему. Это происходит, когда вы удаляете все грани своего графика.

Answer 2

Вы хотите перебрать все вершины.