Comments 8
Во-первых, стоит в начале статьи дать определение эйлеровому пути.
Во-вторых, где у вас тут "ребра вместо вершин". У вас похоже самый обычный алгоритм, основанный на вычеркивании циклов.
И главное, реализация у вас очень-очень неэффективная. Из-за того, что вы проходите каждое ребро в каждом рекурсивном вызове, да еще и ищите его в списке каждый раз, ваш dfs работает за O(E^3), Хотя должен рабоать за O(E). Реализация есть по ссылке выше. Надо для каждой вершины хранить счетчик уже пройденных ребер и в каждой итерации цикла брать первое неиспользованное ребро, вместо цикла по всем элементам массива исходящих ребер (обратите внимание, оно может измениться в рекурсивном вызове). Фактически, это эффективная реализация удаления ребра из графа, как описано в оригинальном алгоритме.
Ну, и не надо пытаться запускать dfs от каждой вершины. Тут даже правильная реализация рекурсивного алгоритма будет работать за квадрат на графах, где эйлерового пути/цикла нет. А ваша реализация будет работать вообще за O(VE^3). Более неэффективную реализацию придумать сложно, даже если попытаться.
Надо посчитать степени вершин (сколько ребер из них выходит) и найти все с нечетными степенями. Если таких 0, то цикл найдется из любой вершины. Если их 2, то можно запуститься из любой из них и найдется путь. В противном случае никаких эйлеровых циклов/путей в графе нет. Ну, еще, наверно, стоит проверить, что найденный путь содержит нужное количество ребер, ибо если граф несвязен, то вы найдете лишь путь по одной компоненте.
ваш dfs работает за O(E^3)
Разве была претензия на более низкую алгоритмическую сложность по сравнению с существующими алгоритмами? Справочнику - привет.
где у вас тут "ребра вместо вершин"
Именно "ребра вместо вершин". Возьмите обычный поиск с возвратом, который работает именно с вершинами.
graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']}
#
print('\n __find_path')
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not start in graph:
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None
print(find_path(graph, 'A', 'D')) # ['A', 'B', 'C', 'D']Ну, и не надо пытаться запускать dfs от каждой вершины
Задача ведь не только в том, чтобы определить является граф Эйлеровым или полу-Эйлеровым. Задача показать из каких стартовых вершин Эйлеровый путь находится, а из каких нет. Не заметили?
Разве была претензия на более низкую алгоритмическую сложность по сравнению с существующими алгоритмами?
Тем не менее, факт что ваша реализация известного алгоритма весьма неэффективна, стоит указать. Чтобы никто из читающих случайно не стал использовать вашу реализацию.
Задача показать из каких стартовых вершин Эйлеровый путь находится, а из каких нет. Не заметили?
Про это я уже написал: "Если таких 0, то цикл найдется из любой вершины. Если их 2, то можно запуститься из любой из них и найдется путь. В противном случае никаких эйлеровых циклов/путей в графе нет."
Все еще не надо запускаться из каждой вершины, особенно чтобы понять, что пути в графе нет.
Откуда у вас edgeSet в контексте функции dfs?
И кстати, у вас тут не backtracking. У вас тут никакого отката назад нет - однажды пройденные ребра больше никогда не пройдутся.
Backtrack(x) if x is not a solution return false if x is a new solution add to list of solutions backtrack(expand x)
Приношу извинения, невнимательно прочитал код. На всякий случай, вот оптимальное решение задачи об Эйлеровом пути, без бэктракинга и работающий за линию:
def dfs(g, v, path, used, reverse_id):
while used[v] < len(g[v]):
used[v] = used[v] + 1
u = g[v][used[v]-1]
reverse_num = reverse_id[v][used[v]-1]
if reverse_num >= used[u]: # Обратное ребро еще не использовано.
dfs(g, u, path, used, reverse_id)
path.append(v);Правда, чтобы работать с неориентированным графом, ему надо знать, где в списке смежности для конца ребра лежит ему обратное. Можно построить эту структуру так:
def ConstructReverse(g):
# Для каждой строки, для каждого значения считаем на каких
# индексах это значение встречается.
where = {v:{} for (v, e) in g.items()}
for v in g:
for (idx, e) in enumerate(g[v]):
if e not in where[v]: where[v][e] = []
where[v][e].append(idx)
# Используя where, считаем для каждого ребра, где в списке
# для второй вершины лежит его обратное.
reverse = {v: [0]*len(e) for (v, e) in g.items()}
for v in g:
for (idx, e) in enumerate(g[v]):
reverse[v][idx] = where[e][v][-1]
where[e][v].pop()
return reverseНу и вызывать это все удовольствие надо так:
def FindEulerPath(g):
good_starts = [v for (v,edges) in g.items() if len(edges) % 2 == 1]
if good_starts and len(good_starts) != 2: return []
start = good_starts[0] if good_starts else next(iter(g.keys()), None)
path = []
used = [0]*(len(g)+1)
dfs(g, start, path, used, ConstructReverse(g))
return path
G3 = {
1: [2, 3, 5, 7],
2: [1, 4, 5, 6],
3: [1, 4, 5, 7],
4: [2, 3, 5, 6],
5: [1, 2, 3, 4],
6: [2, 4],
7: [1, 3]
}
print (FindEulerPath(G3))
Поиск цикла Эйлера алгоритмом backtracking