Гамильтонов путь в простом DAG
Я пытаюсь реализовать рекурсивный поиск гамильтонова пути в простом DAG. Вот данные и код моей игрушки:
DAG в формате Edge-List
4 5
1 2
3 1
3 2
4 3
4 2
DAG в формате словаря после преобразования
{1: [2], 3: [1, 2], 4: [3, 2]}
Код: G - это граф, размер - это количество вершин в графе, v - текущая вершина, v_next - соседняя вершина.
def hamilton(G, size, v, path=[]):
if v not in set(path):
path.append(v)
if len(path) == size:
return path
for v_next in G.get(v, []):
cur_path = [i for i in path]
result = hamilton(G, size, v_next, cur_path)
if result is not None:
return result
else:
print('')
Когда я перебирал вершину (от 1 до 4) и запускал функцию в каждом цикле, результат был немного странным.
for vertex in range(1, v+1):
result = hamilton(graph, v, vertex)
print(result)
None
None
None
[1, 2, 3, 4]
Я ожидаю, что результат будет [4, 3, 1, 2] при запуске с 4. Одно сообщение, упомянутое перед этим, связано с проблемой "изменяемых аргументов по умолчанию". Но я не знаю, как решить в этом случае. Есть подсказки?