トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

グラフアルゴリズム

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

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

グラフアルゴリズム

指針

  詳しい解説

  ビジュアル的にわかる解説

  幅優先探索のQueueの実装をどうするか?

元々のQueueの定義はこう

そしてRubyのArrayの実装はこう

  • Queue自体はArrayで実装
    • enqueueをArray#push
    • dequeueをArray#shift

が見た目的に正しいということになる

array = [1,2,3]

puts "original !"
puts array.to_s

puts "enqueue! 4"
array.push(4)
puts array.to_s

puts "dequeue! 1"
array.shift
puts array.to_s

  幅優先探索の最短距離取得の実装をどうするか?

競技プログラミング必須のアルゴリズムのように感じる

  AOJの関連する問題

ALDS1_11_A

  • Solution for ALDS1_11_A: Graph by hiroyuking
    • N個の頂点があるグラフをN * Nの行列で表すことを隣接行列と言うようだ(頭いい考えだな〜)
    • N個の頂点があった場合、そのうち1つのある頂点Aから他の頂点へつながる数はN-1…
    • 頂点AからAに対する数も含むような行列になってしまうがそれは気にしない
# coding: utf-8
#lines = <<'EOS'
#4
#1 2 2 4
#2 1 4
#3 0
#4 1 3
#EOS
 
lines = $stdin.read
array = lines.split("\n")
 
N = array[0].to_i
 
m = Array.new(N).map{Array.new(N, 0)}
 
for i in 1...array.length
  elems = array[i].split(" ").map(&:to_i)
  u = elems[0]
  k = elems[1]
  v = elems.drop(2) # Array#tail ?????????
 
  #puts "#{u}, #{k}, #{v.to_s}"
  for j in 0...v.length
    #puts "m[#{u-1}][#{v[j]-1}] = 1"
    m[u-1][v[j]-1] = 1
  end
end
 
for i in 0...N
  puts m[i].join(" ")
end

ALDS1_11_B

この疑似コード通りにロジックを実装すればよい

function 深さ優先探索(v)
    v に訪問済みの印を付ける
    v を処理する
    for each v に接続している頂点 i do
        if i が未訪問 then
            深さ優先探索(i)

またAOJの場合、節点への到達時間と探索の終了時間を記録する必要がある。

lines = $stdin.read
array = lines.split("\n")
 
Node = Struct.new(:u, :k, :v, :visited)
 
class Graph
 
  attr :nodes, :d, :f
 
  def initialize(n)
    @nodes = Array.new(n){ Node.new }
    @d = Array.new(n)
    @f = Array.new(n)
  end
 
  def set_graph_node(u, k, v)
    @nodes[u-1].u = u
    @nodes[u-1].k = k
    @nodes[u-1].v = v
    @nodes[u-1].visited = false
  end
 
  def dfs(start = 0, count = 1)
 
    # puts "visit = #{@nodes[start].to_s}, count = #{count}"
    @nodes[start].visited = true
    @d[start] = count
    count = count + 1
 
    for i in @nodes[start].v
      count = dfs(i-1, count) unless @nodes[i-1].visited
    end
    # puts "visited = #{@nodes[start].to_s}, count = #{count}"
 
    @f[start] = count
    count = count + 1
    count
  end
end
 
N     = array[0].to_i
graph = Graph.new(N)
 
for i in 1...array.length
  seps = array[i].split(" ")
  u = seps.drop(0).first.to_i
  k = seps.drop(1).first.to_i
  v = seps.drop(2).map(&:to_i)
  graph.set_graph_node(u, k, v)
end
 
# puts "Trace all nodes !"
# graph.nodes.each do |node|
#   puts node.to_s
# end
 
# puts ""
# puts "any? ==> #{graph.nodes.any?{|n| n.visited == false }}"
 
start, count = 0, 1
 
while graph.nodes.any?{|n| n.visited == false}
  start = graph.nodes.find_index{|n| n.visited == false }
  count = graph.dfs(start, count)
end
 
# puts "d #{graph.d.to_s}"
# puts "f #{graph.f.to_s}"
 
1.upto(N).each do |n|
  puts "#{n} #{graph.d[n-1]} #{graph.f[n-1]}"
end

ALDS1_11_C

function 幅優先探索(v)
    v に訪問済みの印を付ける
    v をキューに追加
    while キューに要素を含む do
        v ← キューから取り出す
        v を処理
        for each v に接続している頂点 i do
            if i が未訪問 then
                i に訪問済みの印を付ける
                i をキューに追加

Wikipediaの内容だけだとノード間の距離がわからない、以下を参照する

全体のノード数をVとする

配列 dist[u]を用意する
for each u in V
    dist[u] = ∞

function 幅優先探索(v)
    v に訪問済みの印を付ける
    v をキューに追加
    while キューに要素を含む do
        v ← キューから取り出す
        v を処理
        for each v に接続している頂点 i do
            if i が未訪問 then
                i に訪問済みの印を付ける
                dist[i] = dist[v] + 1
                i をキューに追加

またAOJの場合、節点への距離を記録する必要がある。

# Queue
class Array
  alias_method :enqueue, :push
  alias_method :dequeue, :shift
end
 
# u : Index of nodes starting from 1...N
# k : degree of this node
# v : array of vertices connected with this node
# c : :white(=undiscovered), :gray(=frontier), :black(finished searching)
# d : distance when the vertex is first discovered
# pi: predecessor vertex
Node = Struct.new(:u, :k, :v, :c, :d, :pi)
 
class Graph
 
  attr :nodes, true
 
  def initialize(n)
    @nodes = Array.new(n){ Node.new }
  end
 
  def add_graph_node(u, v)
    @nodes[u-1].u = u
    if not v.nil?
      (@nodes[u-1].v ||= []).push(v)
      @nodes[u-1].k = @nodes[u-1].v.length ||= 0
    else
      @nodes[u-1].v = [] if @nodes[u-1].v.nil?
      @nodes[u-1].k = 0
    end
    @nodes[u-1].c = :white
    @nodes[u-1].d = -1
    @nodes[u-1].pi = nil
  end
 
  def reset()
    @nodes.each do |node|
      node.c  = :white
      node.d  = -1
      node.pi = nil
    end
  end
 
  def dist()
    puts "d : #{@nodes.map{|node| node.d}.to_a.to_s}"
    puts "pi: #{@nodes.map{|node| node.pi}.to_a.to_s}"
  end
 
  def bfs(start, queue)
 
    start_idx = (start - 1).to_i
    @nodes[start_idx].c  = :gray
    @nodes[start_idx].d  = 0
    @nodes[start_idx].pi = nil
    queue.enqueue(@nodes[start_idx])
 
    while not queue.empty?
 
      u = queue.dequeue
      break if u.v.nil?
 
      u.v.each do |label|
        v = @nodes[label-1]
        if v.c == :white
          v.c  = :gray
          v.d  = u.d.to_i + 1
          v.pi = u
          queue.enqueue(v)
        end
      end
      u.c = :black
    end
  end
end
 
# start
lines = $stdin.read
array = lines.split("\n")
 
N     = array[0].to_i
graph = Graph.new(N)
 
for i in 1...N+1
  seps = array[i].split(" ")
  u    = seps.drop(0)[0].to_i
  k    = seps.drop(1)[0].to_i
  vs   = seps.drop(2).map(&:to_i)
  #puts "add_graph_node(#{u} <--> #{v})"
  for v in vs
    graph.add_graph_node(u, v)
  end
  graph.add_graph_node(u, nil) if vs.length == 0
end
 
graph.bfs(1, [])
 
graph.nodes.each_with_index do |elem, idx|
    puts "#{idx+1} #{graph.nodes[idx].d.to_i}"
end

ALDS1_11_D

300px-Data_Queue.svg.png ruby-array-op.jpg
お名前: コメント: