Алгоритм поиска с возвратом является хоть и затратным, но зато достаточно универсальным методом. Связан он с перебором вершин графа. Возникает вопрос: можно ли интерпретировать ребра в качестве вершин? Вот эта идея и реализуется.
Код позволяет найти, с учетом стартовой вершины, цикл Эйлера или хотя бы его маршрут (полу-Эйлер). По сути, за вершину в такой интерпретации берется множество из двух соседних вершин. Реализовано в dict_to_setEdge. Что касается dfs, то это стандартная реализация обхода в глубину с возвратом.
# не Эйлер
G1 = {
1: [2, 3, 5],
2: [1, 4, 5],
3: [1, 4, 5],
4: [2, 3, 5],
5: [1, 2, 3, 4]
}
# полу-Эйлер
G2 = {
1: [2, 3, 5],
2: [1, 4, 5, 6],
3: [1, 4, 5],
4: [2, 3, 5, 6],
5: [1, 2, 3, 4],
6: [2, 4]
}
# Эйлер
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]
}
def dfs(g, v, path):
#print("path =", path)
if len(path)-1 == len(edgeSet):
return path
for w in g[v]:
if not {v, w} in path:
path.append({v, w})
newpath = dfs(g, w, path)
if newpath:
return newpath
path.pop()
def dict_to_setEdge(G):
s = []
for v in G:
for z in G[v]:
if not {v, z} in s:
s.append({v, z})
return s
v = [1, 2]
for i,g in enumerate([G1, G2, G3]):
edgeSet = dict_to_setEdge(g)
print("==== граф ===", i+1)
for s in v:
print(" для вершины =", s)
p = dfs(g, s, [{s, None}])
if not p:
print("Эйлер и полу-Эйлер не найдены")
elif len({s, None}.intersection(p[-1])):
print("Эйлер найден", p[1:])
else: print("Полу-Эйлер найден", p[1:])
print()
Теперь модифицируем формат данных так, чтобы была возможность обработки мульти-графов. Для этого, во-первых, добавим именованные ребра. Во-вторых, к двум смежным вершинам (3,7) добавим еще одно ребро (для G5) или еще два ребра (для G4). Соответственно, G4 Эйлеровым графом останется.
# Эйлер
G4 = {
1: [(2,1), (3,1), (5,1), (7,1)],
2: [(1,1), (4,1), (5,1), (6,1)],
3: [(1,1), (4,1), (5,1), (7,1), (7,2), (7,3)],
4: [(2,1), (3,1), (5,1), (6,1)],
5: [(1,1), (2,1), (3,1), (4,1)],
6: [(2,1), (4,1)],
7: [(1,1), (3,1), (3,2), (3,3)]
}
# не Эйлер
G5 = {
1: [(2,1), (3,1), (5,1), (7,1)],
2: [(1,1), (4,1), (5,1), (6,1)],
3: [(1,1), (4,1), (5,1), (7,1), (7,2)],
4: [(2,1), (3,1), (5,1), (6,1)],
5: [(1,1), (2,1), (3,1), (4,1)],
6: [(2,1), (4,1)],
7: [(1,1), (3,1), (3,2)]
}
def dfs(g, v, path):
#print("path =", path)
if len(path)-1 == len(edgeSet):
return path
for w in g[v]:
if not ({v, w[0]}, w[1]) in path:
path.append(({v, w[0]}, w[1]))
newpath = dfs(g, w[0], path)
if newpath:
return newpath
path.pop()
def dict_to_setEdge(G):
s = []
for v in G:
for z in G[v]:
if not ({v, z[0]}, z[1]) in s:
s.append(({v, z[0]}, z[1]))
return s
v = [1, 2]
for i,g in enumerate([G4, G5]):
edgeSet = dict_to_setEdge(g)
#print(edgeSet); input()
print("\n==== граф ===", i+1)
for s in v:
print("для вершины =", s)
p = dfs(g, s, [{s, None}])
if not p:
print("Эйлер и полу-Эйлер не найден")
elif len({s, None}.intersection(p[-1][0])):
print("Эйлер найден", p[1:])
else: print("Полу-Эйлер найден", p[1:])
print()
Вот и все.
Комментарии (8)
ReadOnlySadUser
29.03.2024 15:33Откуда у вас edgeSet в контексте функции dfs?
bvv2311 Автор
29.03.2024 15:33Почему так странно использую? Есть варианты с разными выборками (и с решением других задач) из setEdge (без обсчёта ({v, w[0]}, w[1]). Но суть, применительно к статье, все равно одна.
wataru
29.03.2024 15:33И кстати, у вас тут не backtracking. У вас тут никакого отката назад нет - однажды пройденные ребра больше никогда не пройдутся.
bvv2311 Автор
29.03.2024 15:33Backtrack(x) if x is not a solution return false if x is a new solution add to list of solutions backtrack(expand x)
wataru
29.03.2024 15:33Приношу извинения, невнимательно прочитал код. На всякий случай, вот оптимальное решение задачи об Эйлеровом пути, без бэктракинга и работающий за линию:
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))
wataru
Во-первых, стоит в начале статьи дать определение эйлеровому пути.
Во-вторых, где у вас тут "ребра вместо вершин". У вас похоже самый обычный алгоритм, основанный на вычеркивании циклов.
И главное, реализация у вас очень-очень неэффективная. Из-за того, что вы проходите каждое ребро в каждом рекурсивном вызове, да еще и ищите его в списке каждый раз, ваш dfs работает за O(E^3), Хотя должен рабоать за O(E). Реализация есть по ссылке выше. Надо для каждой вершины хранить счетчик уже пройденных ребер и в каждой итерации цикла брать первое неиспользованное ребро, вместо цикла по всем элементам массива исходящих ребер (обратите внимание, оно может измениться в рекурсивном вызове). Фактически, это эффективная реализация удаления ребра из графа, как описано в оригинальном алгоритме.
Ну, и не надо пытаться запускать dfs от каждой вершины. Тут даже правильная реализация рекурсивного алгоритма будет работать за квадрат на графах, где эйлерового пути/цикла нет. А ваша реализация будет работать вообще за O(VE^3). Более неэффективную реализацию придумать сложно, даже если попытаться.
Надо посчитать степени вершин (сколько ребер из них выходит) и найти все с нечетными степенями. Если таких 0, то цикл найдется из любой вершины. Если их 2, то можно запуститься из любой из них и найдется путь. В противном случае никаких эйлеровых циклов/путей в графе нет. Ну, еще, наверно, стоит проверить, что найденный путь содержит нужное количество ребер, ибо если граф несвязен, то вы найдете лишь путь по одной компоненте.
bvv2311 Автор
Разве была претензия на более низкую алгоритмическую сложность по сравнению с существующими алгоритмами? Справочнику - привет.
Именно "ребра вместо вершин". Возьмите обычный поиск с возвратом, который работает именно с вершинами.
Задача ведь не только в том, чтобы определить является граф Эйлеровым или полу-Эйлеровым. Задача показать из каких стартовых вершин Эйлеровый путь находится, а из каких нет. Не заметили?
wataru
Тем не менее, факт что ваша реализация известного алгоритма весьма неэффективна, стоит указать. Чтобы никто из читающих случайно не стал использовать вашу реализацию.
Про это я уже написал: "Если таких 0, то цикл найдется из любой вершины. Если их 2, то можно запуститься из любой из них и найдется путь. В противном случае никаких эйлеровых циклов/путей в графе нет."
Все еще не надо запускаться из каждой вершины, особенно чтобы понять, что пути в графе нет.