練習のための問題は 競技プログラミングの履歴
グラフの距離を測るという点では グラフアルゴリズム の深さ優先探索や幅優先探索の発展版ということができる気がする。
プリム法
詳しい解説
疑似コード
AOJの関連する問題
ALDS1_12_A
このアルゴリズムでは1つの辺から始めて、全頂点を覆うようになるまで連続的に木の大きさを拡大していく。
- 入力: 重み付きグラフ（頂点集合 V、辺集合 E）
- 出力: Vnew と Enew が最小全域木を表している。
実践的なところに行くと、Wikipediaの記述はわかりにくい、
- 再び参照したサイト from ヨークカレッジ ペンシルバニア校/York College of Pennsylvania
疑似コード
PRIM(G,w,r)
for each u ∈ G.V
u.key = ∞
u.pi = NIL
r.key = 0
Q = G.V
while Q ≠ ∅
u = EXTRACT-MIN(Q)
for each v ∈ G.Adj[u]
if v ∈ Q and w(u,v) < v.key
v.pi = u
v.key = w(u,v)
Rubyに落とし込む
INF = Float::INFINITY
Node = Struct.new(:u, :d, :c, :p)
class Graph
attr :nodes, :mat
def initialize(n, matrix)
@nodes = Array.new(n){ Node.new }
@nodes.map.with_index do |node,idx|
node.u = idx
node
end
@mat = matrix.dup
end
def edge_exists?(row, col)
result = if @mat[row][col] != -1
true
else
false
end
result
end
def gen_uniq_edges()
edges = []
@nodes.each_with_index do |node,i|
mat[i].map.with_index.select do |w,idx|
w != -1
end.each do |w,idx|
edge = [node.u, idx].sort
edges << edge
end
end
edges.uniq
end
def prim(start = 0)
@nodes = @nodes.each do |node|
node.d = INF
node.p = nil
node.c = :white
end
@nodes[start].d = 0
@nodes[start].p = -1
next_u = nil
while true
mincost = INF
@nodes.each do |node|
if node.c != :black and node.d < mincost
mincost = node.d
next_u = node.u
end
end
#puts "mincost = #{mincost}, next_u = #{next_u}"
break if mincost == INF
@nodes[next_u.to_i].c = :black
@nodes = @nodes.map.with_index do |node, v|
if node.c != :black and edge_exists?(next_u, v) and mat[next_u-1][v-1] < node.d
node.d = mat[next_u][v]
node.p = next_u
node.c = :gray
#puts " update: node(#{node.u}), d = #{node.d}, parent = #{next_u}"
node
else
node
end
end
end
end
end
- グラフをGraphvizでビジュアル化する
- Webgraphviz のサイトでグラフを見える化できる
graph beforeG {
"1" -- "2" [label=2]
"1" -- "3" [label=3]
"1" -- "4" [label=1]
"2" -- "4" [label=4]
"3" -- "4" [label=1]
"3" -- "5" [label=1]
"4" -- "5" [label=3]
}
graph afterG {
"1" -- "2" [label="w=2 (4)", penwidth=3]
"1" -- "3" [label="w=3"]
"1" -- "4" [label="w=1 (1)", penwidth=3]
"2" -- "4" [label="w=4"]
"3" -- "4" [label="w=1 (2)", penwidth=3]
"3" -- "5" [label="w=1 (3)", penwidth=3]
"4" -- "5" [label="w=3"]
}
- この重み付きグラフの最小全域木を見に行くと…
- こうなるはず（人の目で見ると簡単）
解答
INF = 999999999
Node = Struct.new(:u, :d, :c, :p)
class Graph
attr :nodes, :mat
def initialize(n, matrix)
@nodes = Array.new(n){ Node.new }
@nodes.each_with_index{|node,idx| node.u = idx+1}
@mat = matrix.dup
end
def edge_exists?(row, col)
#printf " edge_exists?(#{row}, #{col}) => "
row -= 1
col -= 1
result = if @mat[row][col] != -1 # or @mat[col][row] != -1
true
else
false
end
#puts "#{result} => cost: #{@mat[row][col]}"
result
end
def gen_uniq_edges()
edges = []
@nodes.each_with_index do |node,i|
mat[i].map.with_index.select do |w,idx|
w != -1
end.each do |w,idx|
edge = [node.u, idx+1].sort
edges << edge
end
end
edges.uniq
end
def dot_before_prim()
puts "graph beforePrim {"
gen_uniq_edges.each do |e|
puts " \"#{e.first}\" -- \"#{e.last}\" [label=#{mat[e.first-1][e.last-1]}]"
end
puts "}"
end
def prim(start = 1)
@nodes = @nodes.each do |node|
node.d = INF
node.p = nil
node.c = :white
end
start = (start-1).to_i
@nodes[start].d = 0
@nodes[start].p = -1
next_u = nil
while true
mincost = INF
@nodes.each do |node|
if node.c != :black and node.d < mincost
mincost = node.d
next_u = node.u
end
end
#puts "mincost = #{mincost}, next_u = #{next_u}"
break if mincost == INF
@nodes[(next_u-1).to_i].c = :black
@nodes = @nodes.map.with_index(1) do |node, v|
if node.c != :black and edge_exists?(next_u, v) and mat[next_u-1][v-1] < node.d
node.d = mat[next_u-1][v-1]
node.p = next_u
node.c = :gray
#puts " update: node(#{node.u}), d = #{node.d}, parent = #{next_u}"
node
else
node
end
end
end
end
end
lines = $stdin.read
array = lines.split("\n")
N = array[0].to_i
mat = Array.new(N).map{Array.new(N, 0)}
for i in 1..N
row = i - 1
cols = array[i].split(" ").map(&:to_i)
cols.each_with_index do |col, idx|
mat[row][idx] = col
end
end
graph = Graph.new(N, mat)
graph.prim(1)
sum = 0
graph.nodes.each_with_index do |n,i|
if graph.nodes[i].p != -1
sum += mat[i].detect do |e|
e != -1 and e == n.d
end
end
end
#puts graph.dot_before_prim
puts sum
graph-prim.png
graph-prim2.png