縦型探索をrubyに翻訳した。

今回は「アルゴリズム事典」で紹介されている縦型探索をrubyに翻訳した。

これは、「深さ優先探索」と言う名前のほうが馴染みがある人も多いのでは。
複数ある指標のうちの1つを固定し、探索不能なところまで行ったら戻ってきて再度探索する、という手法である。

今回もC言語で書かれているアルゴリズム事典のソースコードを、rubyで書き直してみた。
この実装に関しては、本文中のコードでは完結しておらず、サポートサイトからソースコードを入手して参照する必要がある。（readgraph関数について、本文中には記載がない。）

readgraph関数は、与えられたデータを元に点と点の関係を多重配列に格納する。
この多次元配列を元に、再帰的にvisit関数を呼び出すことで各点のつながりを結果として表示している。
NMAX=100としているが、これはCで書く上での配列の大きさの定義なので、考えるグラフのサイズに合わせて変更できるようにしてもよいかも。

翻訳することでfor文が見やすくなるので、非常に良い。
個人的に「rubyでは0をfalseと見なしてくれない（true扱いになる）」という仕様にハマり、思ったような結果が出力できていなかった。
あとは、多重配列の定義さえできればなんとかなる。

これらを踏まえて翻訳すると、以下のようになる。

NMAX = 100
$adjacent = Array.new(NMAX + 1).map{Array.new(NMAX + 1, false)}

$n = 7
$data = [1,2,2,3,1,3,2,4,5,7]

def readgraph
  i = j = 0
  (0..$data.length).each do |k|
    if k.even?
      i = $data[k]
    else
      j = $data[k]
      $adjacent[i][j] = $adjacent[j][i] = true
    end
  end
  puts '隣接行列:'
  (1..$n).each do |i|
    (1..$n).each do |j|
      print " #{$adjacent[i][j] ? 1 : 0}"
    end
    puts
  end
end

$visited = Array.new(NMAX + 1, false)

def visit(i)
  print " #{i}"
  $visited[i] = true
  (1..$n).each do |j|
    visit j if $adjacent[i][j] &amp;&amp; !$visited[j]
  end
end

readgraph

puts '連結成分:'
count = 0

(1..$n).each do |i|
  if !$visited[i]
    count += 1
    print "#{count}:"
    visit i
    puts
  end
end