NetworkXのPrimアルゴリズム(インスタンス解説)

序論

PrimアルゴリズムはDijkstraの最短経路アルゴリズムと似ており、 greedy ポリシーを使用しています。アルゴリズムの開始時、図の重みが最小の辺をTに追加し、次に重みが最小の辺E（Eの1つの端点がTに、もう1つの端点がG-T中）。条件に合ったEが存在しない場合、アルゴリズム終了、その場合TはGの最小生成樹です。

NetworkXはPythonのソフトウェアパッケージで、複雑なネットワークの作成、操作、および複雑なネットワークの構造、動力学、機能の学習に使用されます。 この記事では、networkx.Graphクラスを使用してPrimアルゴリズムを実装しています。

本文

Primアルゴリズムのコード

Prim

def prim(G, s):
 dist = {} # distは節点への最小距離を記録
 parent = {} # parentは最小生成樹の親表を記録
 Q = list(G.nodes()) # Qにはすべての未被生成樹カバーされた節点が含まれる
 MAXDIST = 9999.99 # MAXDISTは無限大を表す、つまり、2つの節点が隣接していない場合
 # データ初期化
 # すべての節点の最小距離をMAXDISTに設定、親節点をNoneに設定
 for v in G.nodes():
  dist[v] = MAXDIST
  parent[v] = None
 # 開始節点sへの距離を0に設定
 dist[s] = 0
 # 不断にQから「最近」の節点を取り出し、最小生成樹に加える
 # Qが空である場合、ループを停止し、アルゴリズム終了
 while Q:
  # 最も「近い」節点uを取り出し、uを最小生成樹に加える
  u = Q[0]
  for v in Q:
   if (dist[v] < dist[u]):
    u = v
  Q.remove(u)
  # uの隣接節点の最小距離を更新
  for v in G.adj[u]:
   if (v in Q) and (G[u][v]['weight'] < dist[v]):
    parent[v] = u
    dist[v] = G[u][v]['weight']
 # アルゴリズム終了、親表形式で最小生成樹を返す
 return parent

テストデータ

から	2	3	4	5	6	7	8
1	1.3	2.1	0.9	0.7	1.8	2.0	1.8
2		0.9	1.8	1.2	2.8	2.3	1.1
3			2.6	1.7	2.5	1.9	1.0
4				0.7	1.6	1.5	0.9
5					0.9	1.1	0.8
6						0.6	1.0
7							0.5

テストコード

import matplotlib.pyplot as plt
import networkx as nx
g_data = [(1, 2, 1.3), (1, 3, 2.1), (1, 4, 0.9), (1, 5, 0.7), (1, 6, 1.8), (1, 7, 2.0), (1, 8, 1.8), (2, 3, 0.9), (2, 4, 1.8), (2, 5, 1.2), (2, 6, 2.8), (2, 7, 2.3), (2, 8, 1.1), (3, 4, 2.6), (3, 5, 1.7), (3, 6, 2.5), (3, 7, 1.9), (3, 8, 1.0), (4, 5, 0.7), (4, 6, 1.6), (4, 7, 1.5), (4, 8, 0.9), (5, 6, 0.9), (5, 7, 1.1), (5, 8, 0.8), (6, 7, 0.6), (6, 8, 1.0), (7, 8, 0.5)]
def draw(g):
 pos = nx.spring_layout(g)
 nx.draw(g, pos, \\
   arrows=True, \\
   with_labels=True, \\
   nodelist=g.nodes(), \\
   style='dashed', \\
   edge_color='b', \\
   width=2, \\
   node_color='y', \\
   alpha=0.5)
 plt.show()
g = nx.Graph()
g.add_weighted_edges_from(g_data)
tree = prim(g, 1)
mtg = nx.Graph()
mtg.add_edges_from(tree.items())
mtg.remove_node(None)
draw(mtg)

実行結果

以上の「NetworkXのPrimアルゴリズム（実例説明）」が編集者が皆さんに提供した全ての内容です。皆さんに参考になれば幸いです。また、呐喊教程を多くのサポートをお願いします。

声明：本文の内容はインターネットから取得しており、著作権者に帰属します。インターネットユーザーにより自発的に提供され、自己でアップロードされたものであり、本サイトは権利を所有しておらず、編集もされていません。著作権侵害の疑いがある場合は、メールを送信して：notice#oldtoolbag.com（メール送信時は、#を@に置き換えてください。通報し、関連する証拠を提供してください。一旦確認が取れた場合、本サイトは即座に侵害疑いの内容を削除します。）