アルゴリズム | 幅優先探索(breadth first search=BFS)

概要

幅優先探索(breadth first search)

内容

幅優先探索は木やグラフを探索するためのアルゴリズム。
アルゴリズムは根から始まり、隣接ノードから探索する。
全ての隣接ノードを探索し終わったら次の深さのノードを探索する。
別名「横型探索」。

特徴

空間計算量：見つかったノードの記録が必要。O(|V| + |E|)
時間計算量：最悪の場合、全検索になりO(|V| + |E|)
完全性：解がある場合は必ず解決できる
最適性：常に最短の解を見つけることができる

ソースコード

# 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 breadth_first_search(finish)
    first_branch = @branches[@top_key]
    nexts = first_branch.to_a
    while (nexts.size > 0)
      nexts.each {|n|return true if n.finish == finish}
      nexts = get_nexts(nexts)
    end
    false
  end

  private
  def get_nexts(currents)
    nexts = []
    currents.each do |n|
      nexts = nexts + @branches[n.finish] if @branches[n.finish]
    end
    nexts
  end
end

テストコード

# encoding: utf-8
require_relative "../breadth_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: true
    },
    {
    case_no: 2,
    branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}],
    finish: 7,
    expected: true
    },
    {
    case_no: 3,
    branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}],
    finish: 3,
    expected: true
    },
    {
    case_no: 4,
    branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}],
    finish: 4,
    expected: true
    },
    {
    case_no: 5,
    branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}],
    finish: 6,
    expected: true
    },
    {
    case_no: 6,
    branches: [{1 => 7}, {1 => 4}, {2 => 3}, {2 => 5}, {3 => 10}, {3 => 6}, {4 => 6}, {6 => 5}],
    finish: 11,
    expected: false
    },
  ]

  cases.each do |c|
    it "#breadth_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}}

      # when
      actual = graph.breadth_first_search c[:finish]
      # then
      expect(actual).to eq(c[:expected])
    end
  end
end