アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム

No.



4-2

 幅優先探索は、グラフを探索するアルゴリズムです。最初の時点で、自分はある頂点（「始点」

と呼ぶ）の上にいるとします。ただし、グラフの全貌はわかっていません。目的は、始点から辺

を辿りながら頂点を探索していき、指 定 された頂点（「ゴール」と呼ぶ）に辿り着くことです。頂

点に到着すると、その頂点がゴールかどうかを判別できます。幅優先探索とは、頂点を探索する

際、始点に近い頂点から優先的に探索していくものです。

A

C

HF

K G L

E I J

B D

A



G

ゴールとは

A

にい

G

にはてい

A

C

HF

K G L

E I J

B D

A

との

B



C



D

にのと

01

02

分い

とは







 

候補の頂点は「先入れ先出し（

FIFO

）」 の仕組みで管理するので、「 キュー」のデー

タ構造を用いることができます。



1-5



p.032

A

C

HF

K G L

E I J

B D

A

C

HF

K G L

E I J

B D

A

C

HF

K G L

E I J

B D

03

04

05

の

1

つの

選択選択の基

はの

にさの ...