Pythonでプリムのアルゴリズムを使用してMSTを見つけるプログラム

グラフが与えられ、そのグラフから「最小スパニングツリー」（MST）を見つけるように求められたとします。グラフのMSTは、すべての頂点が存在して接続され、サブセットにサイクルが存在しない加重グラフのサブセットです。 MSTの合計エッジ重みがグラフから可能な限り最小であるため、MSTは最小と呼ばれます。したがって、ここではプリムのMSTアルゴリズムを使用して、特定のグラフからMSTの合計エッジウェイトを見つけます。

したがって、入力が次のような場合

、頂点の数（n）は4で、開始頂点（s）=3の場合、出力は14になります。

このグラフのMSTは次のようになります-

このMSTの合計エッジウェイトは14です。

これを解決するには、次の手順に従います-

• 関数mst_find（）を定義します。これにはGがかかります、s
  • distance：=負の無限大の値で初期化されたサイズGの新しいリスト
  • 距離[s]：=0
  • itr：=値Falseで初期化されたサイズGの新しいリスト
  • c：=0
  • Trueの場合は、
    • min_weight：=無限大
    • m_idx：=-1
    • 0からGのサイズの範囲のiの場合、
      • itr [i]がFalseと同じ場合、
        • distance [i]
        • min_weight：=distance [i]
        • m_idx：=i
  • m_idxが-1と同じ場合、
    • ループから抜け出す
  • c：=c + min_weight
  • itr [m_idx]：=True
  • G [m_idx]の値の各ペアi、jについて、do
    • distance [i]：=最小距離[i]、j
• return c

例

理解を深めるために、次の実装を見てみましょう-

 def mst_find（G、s）：distance =[float（ "inf"）] * len（G）distance [s] =0 itr =[False] * len（G）c =0 while True：min_weight =float（ "inf"）m_idx =-1 for i in range（len（G））：if itr [i] ==False：if distance [i]  
入力
 
 4、[（1、2、5）、（1、3、5）、（2、3、7）、（1、4、4）]、3 
 
出力
 
 14