寬度首先搜索鄰接矩陣

所以我創建了一個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

來源

2017-04-12 Noah Trotman

查看使用鄰接表表示法的部分。你正在迭代一個節點的鄰居。找出如何用鄰接矩陣迭代節點的鄰居。 – user2357112

我有一個類似的問題一次，我認爲這是最簡單的只需將您的矩陣轉換爲鄰接列表即：

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

然後，您可以使用規範的（和調試的）廣度優先搜索算法和返回的節點列表。我希望可以幫助

來源

2017-04-12 18:53:12

寬度首先搜索鄰接矩陣

回答

相關問題