Python递归行为怪异

2024-03-28 20:51:04 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在用python编写以下程序:

def find_graph(graph, start, end, path=[]):
    f=0
    if start==end:
        if start in graph:
            return start
    if not start in graph:
        return None
    if not end in graph.values():
        return None
    path.append(start)
    for i in graph[start]:
        if end in graph[start]:
            path.append(end)
            f=1
            break

        else:
            for j in graph[start]:
                if f==1:
                    break
                else:
                    find_graph(graph, j, end, path)


    return path

p=find_graph({'A': ['B','C'], 'B': ['C', 'D'], 'C': 'D', 'D': 'E'}, 'A', 'E')
print(p)

它还没有完成,但我只想知道,它什么时候到了最后一步,也就是说,它完成了路径.附加('E'),则f=1并中断。然后它转到return path行;接下来它应该返回这个值,但是它转到else条件中的find_graph(graph, j, end, path)行。为什么会这样?我把f标记也放进去,只是为了不这样做,但是当它变成return pathf时,我不知道为什么。请帮忙。你知道吗


Tags: pathin程序noneforreturnifnot
1条回答
网友
1楼 · 发布于 2024-03-28 20:51:04

已经好几年了,让我们来解决这个问题。f标志变量在函数返回之前设置为1,因此测试f == 1永远不会为真。这似乎也是一个问题:

if not end in graph.values():
    return None

作为结束节点,'F'可以在'B': ['C', 'D', 'F'],中并且没有子节点,但是即使图形有效,上述操作也会失败。儿童有两种不同的结构,这张图很复杂:

'B': ['C', 'D'], 'C': 'D',

而不是简单地:

'B': ['C', 'D'], 'C': ['D'],

但我们可以解决这个问题。最后,您找不到一个图或一个图中的路径,而是一个图中的所有路径,因此我们需要不同的名称,并确保始终返回一个列表列表(或空列表):

def find_paths(graph, start, end):

    if start not in graph:
        return []

    if start == end:
        return [[start]]

    nodes = list(graph[start])

    if end in nodes:
        return [[start, end]]

    paths = []

    for node in nodes:
        for sub_path in find_paths(graph, node, end):
            paths.append([start] + sub_path)

    return paths

print(find_paths({'A': ['B', 'C'], 'B': ['C', 'D'], 'C': 'D', 'D': 'E'}, 'A', 'E'))

输出

> python3 test.py
[['A', 'B', 'C', 'D', 'E'], ['A', 'B', 'D', 'E'], ['A', 'C', 'D', 'E']]
>

我们可以看到,从“A”到“E”有三条路径,代码比您尝试编写的要简单。你知道吗

相关问题 更多 >