所以我创建了一个 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
最佳答案
我曾经遇到过类似的问题,我认为最简单的方法是将矩阵转换为邻接表,即:
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
然后您可以对返回的节点列表使用您的规范(和调试)广度优先搜索算法。希望对您有所帮助
关于python - 使用邻接矩阵进行广度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43375515/