練習のための問題は 競技プログラミングの履歴
グラフの距離を測るという点では グラフアルゴリズム の深さ優先探索や幅優先探索の発展版ということができる気がする。
プリム法
詳しい解説
疑似コード
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