python - 使用邻接矩阵进行广度优先搜索

Question

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

邻接表:

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

邻接矩阵:

[ [0,1,1,1,0], 
  [1,0,1,1,0], 
  [1,1,0,0,1], 
  [1,1,0,0,0], 
  [0,0,1,0,0] ]

---

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

然后您可以对返回的节点列表使用您的规范(和调试)广度优先搜索算法。希望对您有所帮助