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

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

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

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

  深さ優先探索 - アルゴリズムとデータ構造 - Aizu Online Judge

  • u は頂点の番号、k は u の出次数、v は u に隣接する頂点の番号を示します

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

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

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

+ ALDS1_11_B.rb

  応用

lines = $stdin.read
array = lines.split("\n")
 
#
# :u ノードのインデックス
# :k u の出次数
# :v u に隣接する頂点の番号
# :visited 訪問したかどうか
#
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 add_graph_node(u, k)
    @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].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
お名前: コメント: