プリム法

[アルゴリズム,グラフアルゴリズム]

練習のための問題は 競技プログラミングの履歴

グラフの距離を測るという点では グラフアルゴリズム の深さ優先探索や幅優先探索の発展版ということができる気がする。

プリム法

  詳しい解説

• Wikipedia - プリム法

疑似コード

  AOJの関連する問題

• 最小全域木 - アルゴリズムとデータ構造 - Aizu Online Judge

ALDS1_12_A

• Wikipedia - プリム法

このアルゴリズムでは1つの辺から始めて、全頂点を覆うようになるまで連続的に木の大きさを拡大していく。

• 入力: 重み付きグラフ（頂点集合 V、辺集合 E）
• 出力: Vnew と Enew が最小全域木を表している。

実践的なところに行くと、Wikipediaの記述はわかりにくい、

• 再び参照したサイト from ヨークカレッジ ペンシルバニア校/York College of Pennsylvania
  • Lecture 20: Minimum Spanning Trees - Prim's Algorithm

疑似コード

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