找到从一个顶点到另一个顶点的所有路径

Question

试图找到从起始顶点到结束顶点的所有可能路径。这是我到目前为止。

def all_paths(adj_list, source, destination):

paths = []

for neighbour,_ in adj_list[source]:

    path = [source,neighbour]

    state = ['U'] * len(adj_list)

    state[neighbour] = 'D'

    path = finder(adj_list, neighbour, state, path, destination)

    paths.append(path)

return paths

def finder(adj_list, current, state, path, end):

    for neighbour,_ in adj_list[current]:

        if neighbour == end:

            path.append(neighbour)

            return path

        if state[neighbour] == 'U':

            state[neighbour] = 'D'

            path.append(finder(adj_list, neighbour, state, path, end))

            return path

状态数组是为了确保没有顶点被访问两次（U 未被发现，D 被发现）。通过边连接到 i （Nones 是所述边的权重）

输入是

adj_list = [[(1, None), (2, None)], [(0, None), (2, None)], [(1, None), (0, None)]]

print(sorted(all_paths(adj_list, 0, 2)))

预期的输出是

[[0, 1, 2], [0, 2]]

我的输出是

[[0, 1, 2, [...]], [0, 2, 2, [...], [...]]]

不确定我是如何得到这些点和第二条路径中重复的 2 的？

Answer 1

与您的代码非常相似的逻辑，但经过清理，因为 Python 可以检查项目是否在列表中，因此不使用单独的 'U' 或 'D' 数组。ajs =  [[(1, None), (2, None)], [(0, None), (2, None)], [(1, None), (0, None)]]def paths(node, finish):    routes = []    def step(node, path):        for nb,_ in ajs[node]:            if nb == finish:                routes.append( path + [node, nb] )            elif nb not in path:                step(nb, path + [node])    step(node, [])    return routesprint paths(0,2)

Answer 2

这是获得所需答案的代码变体。也就是说，这是解决问题的一种令人困惑的方法。在我看来，该算法分布在两个函数中，而它应该可以用单个递归函数解决。def main():    adj_list = [        [(1, None), (2, None)],        [(0, None), (2, None)],        [(1, None), (0, None)],    ]    paths = sorted(all_paths(adj_list, 0, 2))    print(paths)def all_paths(adj_list, source, destination):    paths = []    for neighbour, _ in adj_list[source]:        pth = [source, neighbour]        if neighbour == destination:            paths.append(pth)        else:            node = finder(                adj_list,                neighbour,                ['U'] * len(adj_list),                pth,                destination,            )            paths.append(pth + [node])    return pathsdef finder(adj_list, current, state, pth, end):    for neighbour, _ in adj_list[current]:        if neighbour == end:            state[neighbour] = 'D'            return neighbour        elif state[neighbour] == 'U':            state[neighbour] = 'D'            return finder(adj_list, neighbour, state, pth, end)main()例如，这是一个替代实现：def main():    # An adjacency matrix for this example:    #    #    0 - 1    #     \ /    #      2    #    matrix = [        [(1, None), (2, None)],        [(0, None), (2, None)],        [(1, None), (0, None)],    ]    # Print all paths from 0 to 2.    paths = get_paths(matrix, 0, 2)    for p in paths:        print(p)def get_paths(matrix, src, dst, seen = None):    # Setup:    # - Initialize return value: paths.    # - Get an independent seen set.    # - Add the source node to the set.    paths = []    seen = set(seen or [])    seen.add(src)    # Explore all non-seen neighbors.    for nb, _ in matrix[src]:        if nb not in seen:            seen.add(nb)            # Find the subpaths from NB to DST.            if nb == dst:                subpaths = [[nb]]            else:                subpaths = get_paths(matrix, nb, dst, seen)            # Glue [SRC] to the those subpaths and add everything to paths.            for sp in subpaths:                paths.append([src] + sp)    return pathsmain()