python - 查找图中顶点的可达顶点

Question

我的代码在计算图中可到达的顶点时遇到问题。

我有以下图表代码

class Vertices():
    number = 0
    def __init__(self):
        Vertices.number += 1
        self.number = Vertices.number
        self.Reachable= []

我通过以下方式创建图表

a = Vertices()
a.Reachable = [1,2]
b = Vertices()
b.Reachable = [3]
c = Vertices()
c.Reachable= [3]
List = []
List.append(a)
List.append(b)
List.append(c)

因此，作为 a 的顶点 1 有一条到其自身和 b 的边。 b 和 c 的情况类似。

我们可以使用 List 在图上移动，即对于顶点 a，它可以到达 List[trans-1]，其中 trans 指的是 a 的可到达列表(List[0] 和 List[1])

现在在这个图中，我必须计算每个顶点的可达性，即为每个顶点计算它可以到达的顶点。例如，a 可以到达 a、b 和 c

我读到可以使用集合在所有列表中进行深度优先搜索。您能为我提供一个如何继续的解决方案吗？

任何人都可以告诉我如何使用集合，因为我认为它对于这个问题来说非常理想，因为它具有与之相关的并集和差函数...... PS:这不是学校作业......

Answer 1

使用 well-known solution 怎么样？解决你的问题吗？

首先，您需要一个图表的数据结构。您可以将其作为列表字典来执行，其中每个顶点表示为键，可到达的顶点是列表值。

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

如果您将图表示为如上所示，则查找 B 的相邻顶点将只是

neighbours_of_B = graph['B']

和(来自同一站点) 找到所有没有循环的路径将是:

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

并运行它:

find_all_paths(graph, 'A', 'D')

希望有帮助。 请通过上面的链接了解更多相关信息。