最小重み無向グラフのBFSグラフスパン

Question

これはたぶん初心者の質問ですが、グラフで遊んでいて、さまざまな演習でBFS検索を実装しています。私はグラフの最小限の完全な範囲を作成するために私が訪れたエッジの重みを実際どのように追跡するかを考え出すことはできません。私のグラフの形式は次のとおりです。

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

ここで、最初の頂点は1と2の隣接する頂点を持つ0であり、重さはそれぞれ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 

瞬間に私の元のグラフと、それは2あるべき場所この機能は6を返します。これは、各頂点を反復していて、すでに訪問しているにもかかわらず、隣接するウェイトを追加しているためです。 これは実際には最小重み付けされたパスを選択するわけではなく、それが取ったパスの重みを追跡するだけです。私はこれにどのように対処できますか？

長い例：これは、正しい答えは23 をする必要があります134の重量を生成

{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)]} 

私はそれが加重エッジを追跡してから最適なパスを選択することができます行方不明ですいくつかのアルゴリズムがありますこの？ 私はDijkstra's Algorithmを知っていますが、指定された開始点と終了点を持つパスには適していて、完全なグラフスパンではありません。

Answer 1

Dijkastraのアルゴリズムとbfsは、2つの頂点間の最小パスを見つけるのに便利です。最小限のスパニングツリーを探したい場合は、代わりに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 

それは、労働組合-FIND（ばらばらセット）のデータ構造を使用して実装されている。ここ

はリンクです。