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

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 pathsdef 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 routes

print 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 paths

def 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 paths

main()