無向圖的最小權重BFS圖形範圍

這可能是一個初學者問題，但是一直在玩圖形，並且已經在各種練習中實施了BFS搜索。我無法弄清楚如何實際跟蹤我訪問過的邊緣的權重，以創建圖的最小完整範圍。我的圖形格式如下：無向圖的最小權重BFS圖形範圍

{0: [(1, 1), (2, 1)], 1: [(0, 1), (2, 1)], 2: [(1, 1), (0, 1)]}

其中第一個頂點爲0，相鄰頂點1和2的權重分別爲1和1。因此，在更清晰的術語中，圖形字典中的密鑰表示頂點，並且密鑰值中的每個元組代表頂點，權重對。

因此，我在我的BFS功能是：

def bfs(graph, start): 
    """returns total weight needed to visit 
    each vertice in the graph with the minimum 
    overall weight possible""" 
    if [] in graph.values(): 
     return "Not Possible" 
    weight = 0 
    visited, queue = set(), [start] 
    while queue: 
     vertex = queue.pop(0) 
     if vertex not in visited: 
      visited.add(vertex) 
      for node in graph[vertex]: 
       queue.append(node[0]) 
       weight += node[1] 
    return weight

在我原來的圖形目前，此功能將返回6它應該是2。我認爲這是因爲它正在迭代每個頂點並添加相鄰的權重，即使它們已經被訪問過。這也不會實際選擇最小加權路徑，它只會跟蹤它所採取路徑的權重，無論這可能是什麼。我該如何解決這個問題？

較長的例子：

{0: [(1, 5), (2, 7), (3, 12)], 1: [(0, 5), (2, 9), (4, 7)], 2: [(0, 7), (1, 9), (3, 4), (4, 4), (5, 3)], 3: [(0, 12), (2, 4), (5, 7)], 4: [(1, 7), (2, 4), (5, 2), (6, 5)], 5: [(2, 3), (3, 7), (4, 2), (6, 2)], 6: [(4, 5), (5, 2)]}

由此產生的134的權重，其中正確的答案應該是23 有一些算法，我缺少的是可以跟蹤的加權邊緣，然後從最佳路徑這個？我知道Dijkstra算法，但據我所知，適用於具有指定開始和結束的路徑，而不是完整的圖形跨度？

來源

2017-03-24 Robert Hemingway

Dijkastra的算法和bfs在找到兩個頂點之間的最小路徑時非常有用。但是，如果您想查找最小生成樹，請檢查Kruskal算法。

這裏是鏈接： https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

僞代碼：

KRUSKAL(G): 
1 A = ∅ 
2 foreach v ∈ G.V: 
3 MAKE-SET(v) 
4 foreach (u, v) in G.E ordered by weight(u, v), increasing: 
5 if FIND-SET(u) ≠ FIND-SET(v): 
6  A = A ∪ {(u, v)} 
7  UNION(u, v) 
8 return A

它使用的合併 - 查找（脫節集）的數據結構來實現。

來源

2017-03-24 00:51:46

無向圖的最小權重BFS圖形範圍

回答

相關問題