0

我正在尝试在一个简单的 DAG 中实现对哈密顿路径的递归搜索。这是我的玩具数据和代码：

边缘列表格式的 DAG

4 5
1 2
3 1
3 2
4 3
4 2

转换后字典格式的 DAG

{1: [2], 3: [1, 2], 4: [3, 2]}

代码：G是图，size是图中的顶点数，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 开始时结果将是 [4, 3, 1, 2]。之前提到的一篇文章是因为“可变默认参数”问题。但我不知道在这种情况下如何解决。有什么提示吗？

4

0 回答 0