带邻接矩阵的广度优先搜索

Question

所以我创建了一个bfs遍历，它使用一个图和一个起点。它使用相邻列表中表示的一个图，但如何将其更改为使用邻接矩阵。我只需要找个地方开始

邻接列表：

{0:[1,2,3],1:[0,2,3],2:[0,1,4],3:[0,1],4:[2]}

邻接矩阵：

^{pr2}$

---

def bfs(graph, v):
  all = []
  Q = []
  Q.append(v)
  while Q != []:
    v = Q.pop(0)
    all.append(v)
    for n in graph[v]:
      if n not in Q and\
      n not in all:
      Q.append(n)
  return all

Answer 1

我曾经遇到过类似的问题，我认为最简单的方法是将矩阵转换为邻接列表，即：

def matrix_to_list(matrix):
    graph = {}
    for i, node in enumerate(matrix):
        adj = []
        for j, connected in enumerate(node):
            if connected:
                adj.append(j)
        graph[i] = adj
    return graph

然后，您可以使用规范的（经过调试的）广度优先搜索算法和返回的节点列表。我希望这有帮助