AOJ - ALDS1_11_A,B,C (グラフアルゴリズム) を解いてみた
AOJ - ALDS1_11は、グラフアルゴリズムです。
グラフの表現 | アルゴリズムとデータ構造 | Aizu Online Judge
深さ優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge
幅優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge
解くと以下の３つを覚えられるのでとても有用です。
どれももっと早く覚えておけばよかったと悔やまれる非常に使いでのあるアルゴリズムです。これらが解けると、以下のAtCoderの問題も解けます（そのままなので…）
アルゴリズム自体の解説はWikipediaとかヨークカレッジペンシルバニア校の授業用の教科書が良かったです。
あと、最初にコレを見たほうが理解が早そう
ALDS1_11_A (隣接行列)
自分の解答
以下メモ
- N個の頂点があるグラフをN * Nの行列で表すことを隣接行列と言うようだ（頭いい考えだな〜）
- N個の頂点があった場合、そのうち１つのある頂点Aから他の頂点へつながる数はN-1…
- 頂点AからAに対する数も含むような行列になってしまうがそれは気にしない
ALDS1_11_B (深さ優先探索)
アルゴリズム
Wikipediaに疑似コードがあるので、それをそのまま実装すれば良い
function 深さ優先探索(v) v に訪問済みの印を付ける v を処理する for each v に接続している頂点 i do if i が未訪問 then 深さ優先探索(i)
自分の解答
ここでもRubyのStructが活躍しており、
- :u → ノードの番号（１〜）
- :k → ノードから出る辺の本数
- :v → 対向ノードの番号（１〜）
- :visited → 訪問したか否か
ぐらいの意味で使っている
Node = Struct.new(:u, :k, :v, :visited)
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 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 (幅優先探索)
アルゴリズム
Wikipediaに疑似コードがあるが、これだと問題がある。あるノードからあるノードへの最短距離がわからない。。。すごく悩んだ
function 幅優先探索(v) v に訪問済みの印を付ける v をキューに追加 while キューに要素を含む do v ← キューから取り出す v を処理 for each v に接続している頂点 i do if i が未訪問 then i に訪問済みの印を付ける i をキューに追加
最終的に、アメリカの大学*1が公開していたアルゴリズムの手順をそのまま実装した。
ポイントはノードに到達したかどうか、探索済みかどうかを３色で表すことだ。また、各ノードへの距離はノード自体のクラスに設定する。
BFS(G,s) for each vertex u ∈ G.V - {s} u.color == WHITE u.d = INF u.pi = NIL s.color = GRAY s.d = 0 s.pi = NIL Q = ∅ ENQUEUE(Q,s) while Q ≠ ∅ u = DEQUEUE(Q) for each v ∈ G.Adj[u] if v.color == WHITE v.color = GRAY v.d = u.d + 1 v.pi = u ENQUEUE(Q,v) u.color = BLACK
自分の解答
いろいろ試してノードのクラスはこんな感じになった。
Node = Struct.new(:u, :k, :v, :c, :d, :pi)
- :u → ノードの番号（１〜）
- :k → ノードから出る辺の本数
- :v → 対向ノードの番号（１〜）
- :c → 訪問状況を３値（＝３色）で
- :d → ノード間の距離の記録
- :pi → 一つ前に探索したノードの記録
# 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
各アルゴリズムをどう使うかなども書きたいのだが、それは後日
