Поиск цикла Эйлера алгоритмом backtracking

Алгоритм поиска с возвратом является хоть и затратным, но зато достаточно универсальным методом. Связан он с перебором вершин графа. Возникает вопрос: можно ли интерпретировать ребра в качестве вершин? Вот эта идея и реализуется.

Код позволяет найти, с учетом стартовой вершины, цикл Эйлера или хотя бы его маршрут (полу-Эйлер). По сути, за вершину в такой интерпретации берется множество из двух соседних вершин. Реализовано в 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()

Вот и все.