概要
深さ優先探索(depth first search)
内容
深さ優先探索は木やグラフを探索するためのアルゴリズム。
別名「縦型探索」。
以下、処理フロー。
・開始点を決める
・隣接するノードへ移動
・ノードがなくなるまで進む
・ノードがなくなったら一つ戻り、未訪問のノードを進む
・全ノードを訪問するまで繰り返す
ソースコード
# encoding: utf-8 require "pp" class Branch attr_accessor :start, :finish def initialize(start, finish) @start, @finish = start, finish end end class Graph attr_accessor :branches, :top_key def initialize(finish) @branches = {} @top_key = 1 @branches[1] = [Branch.new(1, finish)] end def append_branch(start, finish) @branches[start] ||= {} @branches[start] = [] if @branches[start].size == 0 @branches[start] << Branch.new(start, finish) end def depth_first_search(finish) rets = [] first_branch = @branches[top_key] results = depth_first_search_each(first_branch, finish, [], [@top_key]) min = results.min_by {|x|x.size} raise NotExistsAnswerError.new if min.nil? min.size end private def depth_first_search_each(branch, finish, results, parents) complate = false branch.each do |b| tmp = parents.dup tmp << b.finish if b.finish == finish results << tmp next end next if @branches[b.finish].nil? results = depth_first_search_each(@branches[b.finish], finish, results, tmp) end return results end end class NotExistsAnswerError < StandardError;end
テストコード
# encoding: utf-8 require_relative "../depth_first_search" describe Graph do cases = [ { case_no: 1, branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}], finish: 5, expected: 3 }, { case_no: 2, branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}], finish: 7, expected: 2 }, { case_no: 3, branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}], finish: 3, expected: 3 }, { case_no: 4, branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}], finish: 4, expected: 2 }, { case_no: 5, branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}], finish: 6, expected: 3 }, { case_no: 6, branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}], finish: 11, expected: nil, is_error: true, error_class: NotExistsAnswerError }, ] cases.each do |c| it "#depth_first_search case_no=#{c[:case_no]} input=#{c[:branches]} search_no=#{c[:finish]}" do # given graph = Graph.new(2) c[:branches].each {|branch|branch.each {|k, v|graph.append_branch k, v}} if c[:is_error] # when & then lambda {graph.depth_first_search c[:finish]}.should raise_error(c[:error_class]) else # when actual = graph.depth_first_search c[:finish] # then expect(actual).to eq(c[:expected]) end end end end