4. グラフ探索
著者:梅谷 武
グラフ探索の代表的なアルゴリズムである幅優先探索(BFS)と深さ優先探索(DFS)の原理について述べる。
作成:2023-10-14
更新:2024-10-18
4.1 グラフ探索
 グラフGが与えられたとき、その各頂点v∈V(G)にその近傍NG(v)を対応させる写像NG:V(G)→P(V(G))(ここでは近傍を頂点集合とみなす)が定まる。ある頂点v0が与えられたときv0に写像NGを適用することにより到達できるすべての頂点集合を求めること、あるいはその過程で目的となる頂点を見つけることをグラフ探索ぐらふたんさく, graph search(graph search)という。
 ここではグラフ探索の代表的なアルゴリズムである幅優先探索(BFS)と深さ優先探索(DFS)の基本形を実装する。
4.2 幅優先探索(BFS)
 グラフ探索にはまず頂点を入れる容器を用意しなければならない。この容器として先入れ先出し(FIFO: First In, First Out)でデータを管理するキューを用いるのが幅優先探索はばゆうせんたんさく, breadth-first search, BFS(breadth-first search, BFS)である。
 連結グラフGと探索始点v0が与えられたとき、幅優先探索(BFS)は次のように表現できる。
  1. リストvisitedを初期化、visited = '()
  2. キューqueueを初期化、queueにv0をpush
  3. while (queueは空でない)
    • queueからvをpop
    • for (vのすべての近傍点nbr)
      • nbrがvisitedに登録されていなければ登録し、nbrをqueueにpush
  4. visitedを返す。

無向グラフの例2.1

 例2.1の頂点aを探索始点として幅優先探索を行なう。
 bfs-queue.rkt: 
#lang racket
(require "graph.rkt")
 
(define (bfs-queue g start)
  (define visited '())
  (define queue (list start))
  (set! visited (cons start visited))
  (let loop ()
    (when (not (null? queue))
      (displayln queue)
      (define v (car queue))
      (set! queue (cdr queue))
      (displayln v)
      (for ([nbr (neighbors g v)])
        (unless (member nbr visited)
          (set! visited (cons nbr visited))
          (set! queue (append queue (list nbr)))))
      (loop)))
  visited)
 
(define graph21 (make-graph 'undirected))
(add-vertex! graph21 'a)
(add-vertex! graph21 'b)
(add-vertex! graph21 'c)
(add-vertex! graph21 'd)
(add-vertex! graph21 'e)
(add-vertex! graph21 'f)
(add-edge! graph21 'a 'b 'e1)
(add-edge! graph21 'a 'c 'e2)
(add-edge! graph21 'b 'c 'e3)
(add-edge! graph21 'b 'd 'e4)
(add-edge! graph21 'c 'e 'e5)
(add-edge! graph21 'd 'e 'e6)
(add-edge! graph21 'd 'f 'e7)
(add-edge! graph21 'e 'f 'e8)
(add-edge! graph21 'b 'f 'e9)
(add-edge! graph21 'c 'f 'e10)
(add-edge! graph21 'a 'f 'e11)
(add-edge! graph21 'a 'f 'e12)
 
(bfs-queue graph21 'a)



$ racket bfs-queue.rkt
(a)
a
(c b f)
c
(b f e)
b
(f e d)
f
(e d)
e
(d)
d
'(d e f b c a)
4.3 深さ優先探索(DFS)
 頂点を入れる容器として後入れ先出し(LIFO: Last In, First Out)でデータを管理するスタックを用いるのが深さ優先探索ふかさゆうせんたんさく, breadth first search, BFS(depth-first search, DFS)である。
 連結グラフGと探索始点v0が与えられたとき、深さ優先探索(DFS)は次のように表現できる。
  1. リストvisitedを初期化、visited = '()
  2. スタックstackを初期化、stackにv0をpush
  3. while (stackは空でない)
    • stackからvをpop
    • for (vのすべての近傍点nbr)
      • nbrがvisitedに登録されていなければ登録し、nbrをstackにpush
  4. visitedを返す。

無向グラフの例2.1

 例2.1の頂点aを探索始点として深さ優先探索を行なう。
 dfs-queue.rkt: 
#lang racket
(require "graph.rkt")
 
(define (dfs-stack g start)
  (define visited '())
  (define stack (list start))
  (set! visited (cons start visited))
  (let loop ()
    (when (not (null? stack))
      (displayln stack)
      (define v (car stack))
      (set! stack (cdr stack))
      (displayln v)
      (for ([nbr (neighbors g v)])
        (unless (member nbr visited)
          (set! visited (cons nbr visited))
          (set! stack (cons nbr stack))))
      (loop)))
  visited)
 
(define graph21 (make-graph 'undirected))
(add-vertex! graph21 'a)
(add-vertex! graph21 'b)
(add-vertex! graph21 'c)
(add-vertex! graph21 'd)
(add-vertex! graph21 'e)
(add-vertex! graph21 'f)
(add-edge! graph21 'a 'b 'e1)
(add-edge! graph21 'a 'c 'e2)
(add-edge! graph21 'b 'c 'e3)
(add-edge! graph21 'b 'd 'e4)
(add-edge! graph21 'c 'e 'e5)
(add-edge! graph21 'd 'e 'e6)
(add-edge! graph21 'd 'f 'e7)
(add-edge! graph21 'e 'f 'e8)
(add-edge! graph21 'b 'f 'e9)
(add-edge! graph21 'c 'f 'e10)
(add-edge! graph21 'a 'f 'e11)
(add-edge! graph21 'a 'f 'e12)
 
(dfs-stack graph21 'a)



$ racket dfs-stack.rkt 
(a)
a
(f b c)
f
(e d b c)
e
(d b c)
d
(b c)
b
(c)
c
'(e d f b c a)
4.4 再帰的DFS
 深さ優先探索(DFS)は再帰で書かれることが多い。

無向グラフの例2.1

 例2.1の頂点aを探索始点として再帰的に深さ優先探索を行なう。
 dfs-recur.rkt: 
#lang racket
(require "graph.rkt")
 
(define (dfs-recur g current visited)
  (if (member current visited)
      visited
      (for/fold ([visited (cons current visited)])
                ([nbr (neighbors g current)])
        (dfs-recur g nbr visited)))) 
 
(define graph21 (make-graph 'undirected))
(add-vertex! graph21 'a)
(add-vertex! graph21 'b)
(add-vertex! graph21 'c)
(add-vertex! graph21 'd)
(add-vertex! graph21 'e)
(add-vertex! graph21 'f)
(add-edge! graph21 'a 'b 'e1)
(add-edge! graph21 'a 'c 'e2)
(add-edge! graph21 'b 'c 'e3)
(add-edge! graph21 'b 'd 'e4)
(add-edge! graph21 'c 'e 'e5)
(add-edge! graph21 'd 'e 'e6)
(add-edge! graph21 'd 'f 'e7)
(add-edge! graph21 'e 'f 'e8)
(add-edge! graph21 'b 'f 'e9)
(add-edge! graph21 'c 'f 'e10)
(add-edge! graph21 'a 'f 'e11)
(add-edge! graph21 'a 'f 'e12)
 
(dfs-recur graph21 'a '())



$ racket dfs-recur.rkt 
'(e d f b c a)
語　　句
グラフ探索 ぐらふたんさく, graph search
グラフのある頂点に隣接する頂点を辿ることにより到達できるすべての頂点集合を求めること、あるいはその過程で目的となる頂点を見つけること。
幅優先探索 はばゆうせんたんさく, breadth-first search, BFS
キューを使ったグラフ探索アルゴリズムのこと。
深さ優先探索 ふかさゆうせんたんさく, breadth first search, BFS
キューを使ったグラフ探索アルゴリズムのこと。
 
This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani