プリム法
最小全域木問題に対してのプリム法による解法
AOJ ALDS1_12_A Minimum Spanning Tree
・まずスタートの点を決める
・「既に到達した点」から「まだ到達していない点」へ行く辺の中で一番コストの低い辺を探す
・その辺を採用し、辺の先の点は「既に到達した点」に加える
・すべての点に到達したところで最小全域木が完成する
問題文が
点i 点jへのコスト 点j+1へのコスト 点j+2へのコスト
点i+1 点jへのコスト 点j+1へのコスト 点j+2へのコスト
という感じのときに使いやすい
計算量はO(N^2)
でちょっと使いにくいかも
#入力 n = int(input()) A = [] for _ in range(n): a = list(map(int,input().split())) A.append(a) ans = 0 #到達したかどうかのboolリスト used = [False]*n #適当に0番目から開始 used[0] = True #到達した点の数のカウントを行う cnt = 1 while cnt<n: mincost = float("INF") point_temp = -1 #現時点で到達がTrueになっている点の行き先のうちで for i in range(n): if used[i]: for j in range(n): #行き先への到達がTrueになっておらず、-1でもない点のコストを全検索 if used[j]: continue if A[i][j] == -1: continue if A[i][j] < mincost: mincost = A[i][j] point_temp = j if point_temp == -1: print("error") exit() #最小コストだった点をTrueに変更する used[point_temp] = True ans += mincost cnt += 1 print(ans)
クラスカル法、プリム法は
下記のサイトを参考にしました。
ありがとうございます。
algo-logic.info