查找图中顶点的可达顶点

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。

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

Reachable list of a (List[0] and List[1])

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

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

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

Answer 1

使用众所周知的解决方案来解决您的问题怎么样？

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

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

希望有帮助。 请在上面的链接中阅读更多相关信息。

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

首先是

Vertex

，而不是

Vertice

。其次，您（大约）实现了一个“邻接列表”作为图的数据结构；使用邻接矩阵会更标准。 你知道什么是

深度优先搜索

吗？粗略地说，您从一个顶点开始，选择一个邻居，然后选择该顶点的一个邻居，依此类推，直到没有可供选择的邻居。然后你回溯并选择下一个邻居，依此类推。它以递归方式优雅地实现（您以前遇到过吗？），因为问题可以轻松地分成更小的部分：要深度优先搜索图，您只需从任何顶点开始，然后从其所有邻居中进行深度优先搜索转。 具体来说，您需要将问题分解为更小的问题：假设您可以找到从

b

和

c

可到达的节点。从

a

你能到达什么？好吧，

b

，从

b

可以到达的所有内容，

c

，以及从

c

可以到达的所有内容。