5. 根付き全域木
著者:梅谷 武
根付き全域木を幅優先探索(BFS)と深さ優先探索(DFS)で求める。
作成:2023-10-14
更新:2024-10-18
5.1 幅優先探索(BFS)
 連結グラフGの頂点v0が与えられたとき、v0から各頂点への距離(根付き木のレベル)を計算しながら、v0を根とする全域木Tを求める。これを幅優先探索、すなわち先入れ先出し(FIFO: First In, First Out)でデータを管理するキューを使って行なう。
  1. V(T) := V(G), E(T) := ∅
  2. ハッシュ表dを初期化、d(v0) := 0
  3. キューqueueを初期化、queueにv0をpush
  4. while (queueは空でない)
    • queueからvをpop
    • for (vのすべての近傍nbr)
      • nbrがdに登録されていなければ、nbrをqueueにpushし、頂点対(v,nbr)に対応する辺をE(T)に追加し、d(nbr) := d(v) + 1
  5. T = (V(T),E(T))とdを返す。

無向グラフの例2.1

 例2.1の頂点aを根とする全域木を求める。
 bfs-rst.rkt: 
#lang racket
(require data/queue)
(require "graph.rkt")
(require "kruskal.rkt")
 
(define (symbol-add sym1 sym2)
  (string->symbol
    (string-append (symbol->string sym1) "-" (symbol->string sym2))))
 
(define (bfs-rst g start)
  (define vertices (get-vertices g))
  (define rst (make-graph 'directed))
  (for-each (λ (v) (add-vertex! rst v)) vertices)
  (define distances (make-hash))
  (hash-set! distances start 0)
  (define que (make-queue))
  (enqueue! que start)
  (let loop ()
    (if (not (queue-empty? que))
        (let ([v (dequeue! que)])
          (for ([nbr (neighbors g v)])
            (unless (hash-has-key? distances nbr)
              (enqueue! que nbr)
              (define key (make-key v nbr (get-type g)))
              (define edges (hash-ref (get-fibers g) key '()))
              (add-edge! rst v nbr (car edges))
              (hash-set! distances nbr (+ 1 (hash-ref distances v)))))
          (loop))
        (void)))
  (values rst distances))
 
(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)
 
(define-values (rst distances) (bfs-rst graph21 'a))
(displayln distances)
(gen-dot-png graph21 rst "graph21a.dot")



$ racket bfs-rst.rkt
#hash((a . 0) (b . 1) (c . 1) (d . 2) (e . 2) (f . 1))
dot -Tpng graph21a.dot -o graph21a.png
#t
 graph21a.png:
graph21a.png
5.2 深さ優先探索(DFS)
 連結グラフGの頂点v0が与えられたとき、v0から各頂点への距離(根付き木のレベル)を計算しながら、v0を根とする全域木Tを求める。これを深さ優先探索、すなわち後入れ先出し(LIFO: Last In, First Out)でデータを管理するスタックを使って行なう。
  1. V(T) := V(G), E(T) := ∅
  2. ハッシュ表dを初期化、d(v0) := 0
  3. スタックstackを初期化、stackにv0をpush
  4. while (stackは空でない)
    • stackからvをpop
    • for (vのすべての近傍nbr)
      • nbrがdに登録されていなければ、nbrをstackにpushし、頂点対(v,nbr)に対応する辺をE(T)に追加し、d(nbr) := d(v) + 1
  5. T = (V(T),E(T))とdを返す。

無向グラフの例2.1

 例2.1の頂点aを根とする全域木を求める。
 dfs-rst.rkt: 
#lang racket
(require data/queue)
(require "graph.rkt")
(require "kruskal.rkt")
 
(define (symbol-add sym1 sym2)
  (string->symbol
    (string-append (symbol->string sym1) "-" (symbol->string sym2))))
 
(define (dfs-rst g start)
  (define vertices (get-vertices g))
  (define rst (make-graph 'directed))
  (for-each (λ (v) (add-vertex! rst v)) vertices)
  (define distances (make-hash))
  (hash-set! distances start 0)
  (define stack (list start))
  (let loop ()
    (if (not (null? stack))
      (let ()
        (define v (car stack))
        (set! stack (cdr stack))
        (for ([nbr (neighbors g v)])
          (unless (hash-has-key? distances nbr)
            (set! stack (cons nbr stack))
            (define key (make-key v nbr (get-type g)))
            (define edges (hash-ref (get-fibers g) key '()))
            (add-edge! rst v nbr (car edges))
            (hash-set! distances nbr (+ 1 (hash-ref distances v)))))
        (loop))
      (void)))
  (values rst distances))
 
(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)
 
(define-values (rst distances) (dfs-rst graph21 'a))
(displayln distances)
(gen-dot-png graph21 rst "graph21b.dot")



$ racket dfs-rst.rkt
#hash((a . 0) (b . 1) (c . 1) (d . 2) (e . 2) (f . 1))
dot -Tpng graph21b.dot -o graph21b.png
#t
 graph21b.png:
graph21b.png
This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani