Построение Гамильтонова цикла

Question

Дан ориентированный граф, требуется построить Гамильтонов цикл. Не могу понять почему программа неправильно работает. Для примера:

Vertices = 5
Edges = 12
0 4
0 1
1 2
2 1
2 3
3 2
3 4
4 3
0 3
3 0
0 2
4 1
Вывод: 0,1,2,3,4
Ожидаемый результат: 0, 4, 1, 2, 3

n = int(input('Vertices: '))
m = int(input('Edges: '))
adj = [[0] * n for _ in range(n)]

for i in range(m):
    k, l = map(int, input().split())
    adj[k][l] = 1

used = [False] * n
path = []
def hamilton (v):
        path.append(v)
        if len(path) == n:
            if adj[path[0]][path[-1]] == 1:
                return True
            else:
                path.pop()
                return False
        used[v] = True
        for next in range(n):
            if adj[v][next] == 1 and not used[next]:
                if hamilton(next):
                    return True
        used[v] = False
        path.pop()
        return False

for i in range(n):
    hamilton(i)
    print (path)
    path.clear()

Answer 1

Программа выводит неверный ответ, так как неверно условие if adj[path[0]][path[-1]] == 1, вместо этого должно быть написано if adj[path[-1]][path[0]] == 1.

Answer 2

def hamiltomian_circuit(start, vertices, graph):
    result = [start]
    while result:
        if graph[result[-1]]:
            vertex = graph[result[-1]].pop()
            if vertex not in result:
                result.append(vertex)
        else:
            del graph[result[-1]]
            result.pop()
        if len(result) == vertices:
            break
    return result            


vertices = 5
edges = ['0 4', '0 1', '1 2', '2 1', 
         '2 3', '3 2', '3 4', '4 3', 
         '0 3', '3 0', '0 2', '4 1']
origin_graph = {}
for edge in edges:
    source, destination = edge.split()
    if source not in origin_graph:
        origin_graph[source] = []
    origin_graph[source].append(destination)

path = []
for source in origin_graph:
    path = hamiltomian_circuit(source, vertices, origin_graph.copy())
    if path:
        break
print(' '.join(path))  # 0 2 3 4 1 - результат другой, но соответствует условию

БЛОГ НА HUSL

Построение Гамильтонова цикла

Ответы (2 шт):