グラフアルゴリズム - 幅優先探索

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

グラフアルゴリズム - 幅優先探索

  利用例

Wikipedia - 幅優先探索 より

• グラフ内の全ての連結成分をみつける。幅優先探索で到達するノードの集合は初期ノードを含む最大の連結成分である。
• 1つの連結成分内の全てのノードをみつける。
• 辺の重みなしグラフの最小全域木を求める。
• 辺の重みなしグラフの単一始点最短経路問題を解く。
• グラフが2部グラフ(Bipartite graph)かどうかテストする。もし幅優先探索の同じ段階のノード集合に存在するノードに合流する辺があるならば、グラフには奇数長の閉路が存在し2部グラフではない。

  出典

• 幅優先探索 - アルゴリズムとデータ構造 - Aizu Online Judge
  • u は頂点の番号、k は u の出次数、v　は u に隣接する頂点の番号を示します

• 参照したサイト from ヨークカレッジ ペンシルバニア校/York College of Pennsylvania
  • Lecture 16: Breadth-First Search (BFS)

  注意

• How does a Breadth-First Search work when looking for Shortest Path? より重要な指摘

   As pointed above, BFS can only be used to find shortest path in a graph if:
   
   * There are no loops
   * All edges have same weight or no weight.

上で示されるように、幅優先探索は以下の要件を満たすグラフでのみ最短経路を見つけることができる

• ループがない
• すべての辺はすべて同じ重みか、重みがない

• 「辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。」 Wikipedia - ダイクストラ法
  • つまり辺の重みが１の場合は幅優先探索が使えるが、そうでない場合はダイクストラ法を使うべきである

• 幅優先探索 - アルゴリズムとデータ構造 - Aizu Online Judge
  • u は頂点の番号、k は u の出次数、v　は u に隣接する頂点の番号を示します

# 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, d = 0)
    @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 = d
    @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