Tbpgr Blog

Employee Experience Engineer tbpgr(てぃーびー) のブログ

アルゴリズム | 深さ優先探索(depth first search=DFS)

概要

深さ優先探索(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