Поиск цикла Эйлера алгоритмом 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()

Вот и все.