#algorithm #graph #graph-theory
#алгоритм #График #теория графов
Вопрос:
Я реализовал алгоритм для нахождения цикла Эйлера для заданной начальной вершины в неориентированном графе (используя DFS и удаляя посещенные ребра), но он всегда возвращает только один путь. Как мне модифицировать алгоритм для поиска всех возможных циклов Эйлера для вершины?
Вот соответствующий код:
typedef int Graph[200][200]; // adjacency matrix
int v, e; // vertex count, edge count
......
void DFS(Graph amp;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. Можете ли вы опубликовать свою реализацию? Это не должно требовать слишком много изменений.
2. Вы не тестировали мосты? Это не схема Эйлера!? Или есть разница между схемой Эйлера и циклом Эйлера?
3. Да, на данный момент мост не обнаружен. Просто пытаюсь сначала заставить его работать на простых графиках.
Ответ №1:
После рекурсивного вызова вам следует повторно вставить ребра, которые вы удалили ранее, и избавиться от разрыва.
void DFS(Graph amp;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;
}
}
Все, что вам нужно сейчас, это способ выяснить, когда вы сгенерировали полный цикл, чтобы вы могли распечатать его и перейти к следующему. Это происходит, когда вы устраняете все ребра вашего графика.
Комментарии:
1. Хм, похоже, он создает все возможные циклы, а не только эйлеровы. Но в любом случае это очень полезно. Из них очень легко выбрать циклы Эйлера, и я думаю, это именно то, чего от меня ожидали в этой задаче.
Ответ №2:
Вы хотите выполнить цикл через все вершины.
Комментарии:
1. Почему понижающий голос? Разве это не серьезный ответ? Он может попробовать все комбинации?
2. Может быть несколько циклов, начинающихся с одной вершины и зацикливающихся, хотя все вершины этого не решают. Кстати, понижение было не моим.