在 Python 中使用列表的列表以广度优先遍历图

Question

所以我看到广度优先搜索经常使用字典来实现。我只想知道是否可以使用列表的列表来遍历图形。然后返回 parent 数组。 [每个顶点的parents。]如果是这样，怎么样？说，我有一个像这样的邻接列表

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

其中 G 是有向未加权图。因此 NONE。否则它会有一个数字。 vertex(0) 与vertex(1) 和vertex(2) 相邻。顶点 (1) 仅与顶点 (0) 相邻。顶点 (2) 不与任何顶点相邻。

我应该先创建一个新的顶点列表吗？我应该摆脱体重吗？我不确定如何处理这个问题。你能帮忙的话，我会很高兴。谢谢

Answer 1

当然，任何一种方式都可以。您可以这样表示图表：

g = [[1, 2], [0], []]

然后 g[g[j][0]] 返回第 j 个元素的邻接列表中第一个顶点的邻接列表。列表的列表和键为 0,...,n 且值为 int 的列表的字典之间没有区别，但在我看来，除非需要字典，否则列表是一个更明智的想法。如果没有重量，就没有理由为所有重量设置 None。

但是请注意，BFS 将要求您跟踪某个顶点是否已被访问，您可以在跟踪父节点的同时进行此操作：

parents = [None, None, None]

您通常还希望在访问节点时跟踪当前所处的深度（除非您仅测试连接性），您可以这样做：

import collections
Vertex = collections.namedtuple("Vertex", ["idx", "depth"])

现在，当您从队列中弹出一个顶点 v 时，您会遍历其邻接列表中的每个 u_idx。如果 parents[u_idx] is None（尚未访问过），则将 Vertex(u_idx, v.depth + 1) 推入您的队列并标记 parents[u_idx] = v.

Traversing a Graph in Breadth First in Python Using a List of List