Гамильтонов путь в простом 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. Одно сообщение, упомянутое перед этим, связано с проблемой "изменяемых аргументов по умолчанию". Но я не знаю, как решить в этом случае. Есть подсказки?

0 ответов

Другие вопросы по тегам