找到图中一个顶点的可达顶点

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)

所以顶点1，也就是a，有一条边指向自己和b。b和c也是一样。

我们可以通过列表在图中移动，也就是说对于顶点a，它可以到达的地方在列表中是List[trans-1]，这里的trans指的是Reachable list of a (List[0] and List[1])

现在在这个图中，我需要计算每个顶点的可达性，也就是计算每个顶点可以到达哪些其他顶点。例如，a可以到达a、b和c。

我听说可以使用集合来进行深度优先搜索，遍历所有的列表。有人能告诉我该怎么用集合吗？我觉得这对解决这个问题很合适，因为集合有并集和差集的功能……

PS：这不是学校的作业……

Answer 1

首先要说的是，应该是 Vertex，而不是 Vertice。其次，你大概是用邻接表这种数据结构来表示你的图；其实用邻接矩阵会更标准一些。

你知道什么是 深度优先搜索 吗？简单来说，就是从一个顶点开始，选择一个邻居，然后再选择那个邻居的邻居，依此类推，直到没有邻居可以选择为止。然后你就回退，选择下一个邻居，继续这个过程。这个方法可以优雅地用递归来实现（你之前听说过递归吗？），因为这个问题可以很容易地拆分成更小的部分：要进行深度优先搜索，你只需从任意一个顶点开始，然后依次对它的所有邻居进行深度优先搜索。

具体来说，你需要把问题拆分成更小的问题：假设你能找到从 b 和 c 可达的节点。那么从 a 能到达什么呢？其实就是 b、从 b 可达的所有东西、c，以及从 c 可达的所有东西。

Answer 2

你为什么不使用NetworkX或者其他图形库呢？

你现在的表示方法是行不通的。任何函数怎么能从数字2到达顶点b呢？你需要添加实际的对象，而不仅仅是它们的数字。

一旦你这样做了，你就可以像下面这样操作：

def reachable( start ):
    # the set of reachable nodes
    reachable = set()

    # recursive function to add all reachable nodes to `reachable`
    def finder(node):
        reachable.add(node.)
        for other in node.Reachable:
            finder(other)

    # add everything we can reach from here
    finder(start)
    return reachable

Answer 3

你考虑过用一个大家都知道的解决方案来解决你的问题吗？

首先，你需要一个图的数据结构。你可以把它做成一个字典，字典里的每个键代表一个点，而对应的值是一个列表，列表里是可以到达的其他点。

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')

希望这对你有帮助。想了解更多，可以查看上面的链接。