0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

【Ruby】無向グラフでアルゴリズムを学ぶ

0
Posted at

はじめに

プログラミングの能力を高めるため、アルゴリズムの基礎を学びます。
いつもコードを書こうとすると、頭が真っ白な状態に陥ってしまいます。
その原因は足掛かりとなる知識がないからだと思います。
まず、地盤を築き、それ自体を使用もしくは応用したりできる思考力を身に付けることがゴールです。

内容
本記事は、グラフの一種である無向グラフを使って学習を進めます。

テスト
RSpecを利用してテストコードも実装しましたが、記事が長くなるため私のgo-on-ruby-algo-tripリポジトリにあります。

無向グラフ

無向グラフとは、頂点(ノード)と辺からなるグラフの一種です。
辺には方向を持たず、頂点同士の関係を対等に表しています。

形式
グラフ構造は、隣接リストと隣接行列の2通りの方法で表現できます。

使用例
無向グラフは、ネットワークや端末間の相互接続、双方向道路を前提とした地図・経路探索などで使用されています。

コード : 「隣接リスト」

require 'set'

# 無向グラフ(隣接リスト)
class MyUndirectedGraphList
  attr_accessor :adj_list

  def initialize
    @adj_list = Hash.new { |h, k| h[k] = [] }  # デフォルト値に空配列を設定
  end

  # 無向辺を追加
  def add_edge(u, v)
    @adj_list[u] << v unless @adj_list[u].include?(v)
    @adj_list[v] << u unless @adj_list[v].include?(u)
  end

  # グラフ表示
  def show
    @adj_list.map { |node, neighbors| "#{node} => #{neighbors.join(', ')}" }.join("\n")
=begin
    @adj_list.each do |node, neighbors|
      puts "#{node} => #{neighbors.join(', ')}"
    end
=end
  end

  # 深さ優先探索(DFS)
  def dfs(start, visited = Set.new, result = [])
    return result if visited.include?(start)
    #puts "DFS visit: #{start}"
    result << start
    visited.add(start)
    @adj_list[start].each do |neighbor|
      dfs(neighbor, visited, result)
    end
    result
  end

  # 幅優先探索(BFS)
  def bfs(start, result = [])
    visited = Set.new
    queue = [start]

    until queue.empty?
      node = queue.shift
      next if visited.include?(node)
      #puts "BFS visit: #{node}"
      result << node
      visited.add(node)
      queue.concat(@adj_list[node])
    end
    result
  end

  # 辺を削除
  def delete_edge(u, v)
    @adj_list[u]&.delete(v)
    @adj_list[v]&.delete(u)
  end

  # 頂点を削除
  def delete_vertex(u)
    return nil unless @adj_list.key?(u)
  
    @adj_list.delete(u)
    @adj_list.each do |_, neighbors|
      neighbors.delete(u)
    end
  end
end

「Hashインスタンスのデフォルト値の注意点」

Hashクラスのインスタンス生成時にブロックを渡すと、未定義のキーにアクセスしたときブロックが呼び出されて処理されます。
MyUndirectedGraphListのようにブロック内でh[k] = []と書くと、未定義のキー(k)にアクセスしたとき空配列で初期化されます。

adj_list = Hash.new { |h, k| h[k] = [] }
adj_list[:a] << 1
adj_list[:b] << 2

p adj_list[:a]  # => [1]
p adj_list[:b]  # => [2]

Hash.new([])の場合、インスタンス生成と同時に空配列オブジェクトが作成されます。
この配列は ハッシュの各キーで共有されるため、異なるキーを操作しても同じ配列が変更されます。

hash = Hash.new([])
hash[:a] << 1
hash[:b] << 2

p hash[:a]  # => [1, 2]
p hash[:b]  # => [1, 2]

また、空配列オブジェクトはHashインスタンス内部には存在せず、Hashとは関係のない場所に作られます。そのため、インスタンス自体を確認すると以下のように空のままです。

p hash  # => {}

「dfsメソッド」

dfsメソッドは、訪問済みの頂点を記録しながら再帰処理によって探索を行う、深さ優先探索(DFS)の実装です。
開始頂点から到達可能な頂点を可能な限り深く辿り、行き止まりに達した場合は再帰から戻り、未探索の隣接頂点があればそれらを順に探索します。

無向グラフでは、辺で接続された頂点同士が互いに隣接情報を持つため、visitedによる訪問管理を行わないと親子間を往復する無限再帰に陥ります。
そのため、すでに訪問済みの頂点に到達した場合はreturn if visited.include?(start)により再帰処理を打ち切っています。

「Setクラス」

Setは集合クラスであり、重複しない要素の集まりを表します。内部的にはHashを用いており、キーのみを意味のある情報として扱います。
値は存在するが意味を持たないため、[]や[]=による値アクセス・代入は提供されていません。

require "set"

set = Set.new
set.add(1)
p set[1]            # => undefined method `[]'
p set[1] = "value"  # => undefined method `[]='

「bfsメソッド」

bfsメソッドは、起点からの辺の本数が小さい順に探索を進めていく幅優先探索(BFS)手法です。
queue.concat(@adj_list[node])によって、現在の頂点に隣接する各頂点を次の探索候補としてキューの末尾に追加します。 これらの頂点をFIFOで1つずつ取り出して処理することで、探索は距離の近い順に進行します。
dfsメソッドと同様にvisitedによって訪問済みの頂点を除外し、同じ頂点を複数回訪問しないようにしています。

「safe navigation operator &.」

delete_edge(u, v)メソッド内にある&.は、レシーバーがnilでない場合にのみメソッドを呼び出す演算子です。 レシーバーがnilの場合は何もせずnilを返すため、存在しない頂点に対してもエラーを起こさず処理を続けられます。

コード : 「隣接行列」

# 無向グラフ(隣接行列)
class MyUndirectedGraphMatrix
  def initialize(vertices)
    @vertices = vertices
    @size = vertices.size
    @matrix = Array.new(@size) { Array.new(@size, 0) }
    @index = vertices.each_with_index.to_h
  end

  # 無向辺を追加
  def add_edge(u, v)
    i = @index[u]
    j = @index[v]
    @matrix[i][j] = 1
    @matrix[j][i] = 1
  end

  # 辺の有無を確認
  def edge?(u, v)
    i = @index[u]
    j = @index[v]

    @matrix[i][j] == 1
  end

  # 隣接行列を文字列として返す
  def show
    "   #{@vertices.join(' ')}\n" +
    @matrix.each_with_index.map { |row, i| "#{@vertices[i]}  #{row.join(' ')}" }.join("\n")
  end

  # 辺を削除
  def delete_edge(u, v)
    i = @index[u]
    j = @index[v]

    @matrix[i][j] = 0
    @matrix[j][i] = 0
  end

  # 頂点を削除
  def delete_vertex(v)
    del_v = @index[v]

    @matrix.delete_at(del_v)
    @matrix.each { |row| row.delete_at(del_v) }
    
    @vertices.delete_at(del_v) 
    @size -= 1
    @index = @vertices.each_with_index.to_h
  end
end

「設計方針」

MyUndirectedGraphMatrixはMyUndirectedGraphListと異なり、頂点数が増減すると行列全体の構造に大きく影響を与えるため、初期化時に頂点集合を引数として受け取る設計としています。
そのため、学習目的で頂点を削除するメソッドは実装していますが、頂点を追加するメソッドは実装していません。

「initializeメソッド」

インスタンス変数@verticesは、隣接行列の行・列に対応する頂点ラベルの一覧です。
@index = vertices.each_with_index.to_hによって、各頂点ラベルを隣接行列上のインデックス(行・列番号)に対応付けています。具体的には、vertices配列の値をhashキーに、インデックスを要素値としています。

「Arrayインスタンスのデフォルト値の注意点」

Array.newにブロックを渡すと、各要素ごとにブロックが評価されます。
一方で Array.new(n, []) のように引数で配列を渡した場合、その配列は全要素で共有されるため異なるインデックスを操作しても同じ配列が変更されます。

array = Array.new(3, [])
array[0] << 0

p array  # => [[0], [0], [0]]

おわりに

簡易的な実装ではありますが、本課題を通して初めてキューを自作しました。これまでキューは座学や資格試験の問題で見かけることはあったものの、具体的な用途や利点については漠然とした理解にとどまっていました。
今回、グラフ探索において実際にキューを用いることで、幅優先探索(BFS)の仕組みや、キューがどのような場面で有効なのかを具体的に理解することができました。

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?