使用列表列表在Python中首先遍历一个图表使用列表

Question

因此，我看到了使用字典实现的广度优先搜索。我只想知道是否有可能使用列表列表遍历一个图。然后返回父数组。 [每个顶点的父母。]如果是这样，怎么样？说，我有一个邻接列表像这样

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

其中G是一个有向和无权图。因此NONE。否则它会有一个数字。顶点（0）与顶点（1）和顶点（2）都相邻。顶点（1）仅与顶点（0）相邻。顶点（2）不与任何相邻。

我应该首先制作一个新的顶点列表吗？我应该摆脱重量吗？我不知道如何解决这个问题。你能帮忙的话，我会很高兴。谢谢

Answer 1

当然，无论哪种方式都很好。你可以代表你的图是这样的：

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

然后g[g[j][0]]让你回到那个先出现j个元素的邻接表的顶点的邻接表。列表和字典的关键是0,...,n和其值是int s的列表之间没有区别，但在我看来，列表是一个更明智的想法，除非字典是必要的。如果没有重量，没有理由对所有的重量都有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。