ｽﾗｲﾄﾞﾀｲﾄﾙなし

2015. 7.22
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Keiichi MIYAJIMA
幅優先探索
幅優先探索
v1
v8
v2
v6
v3
v4
v7
v5
図のような無向グラフでの横優先探索とは？
幅優先探索
１
v1
v8
v2
v6
v3
v4
v5
V1からスタートすると・・・
v7
幅優先探索
１
v1
２
v8
v2
v6
v3
v4
v5
まずV2を探索
v7
幅優先探索
１
v1
２
v8
v2
v6
v3
v4
３
v5
次にV６を探索
v7
幅優先探索
１
v1
２
v8
v2
v6
v3
v4
３
v5
次にV７を探索
v7
４
幅優先探索
１
v1
２
v8
v2
v6
v3
v4
３
v5
次にV８を探索
v7
４
５
幅優先探索
１
v1
２
v8
v2
v6
v3
v4
３
５
v7
４
v5
Ｖ１と繋がっている全てのノードを探索し終えたの
で、ｖ２からの視点に移る。
幅優先探索
１
v1
２
v8
v2
v3
v4
６
v6
３
５
v7
４
v5
Ｖ１は既に探索済みなので、Ｖ２からｖ３を探索
幅優先探索
１
v1
２
v8
v2
v3
v4
７
６
v6
３
v7
４
v5
Ｖ２から、横優先の方向でｖ４を探索
５
幅優先探索
１
v1
２
v8
v2
v3
v4
７
６
v6
３
５
v7
４
v5
Ｖ６は既に探索済みなので、視点をＶ３へ移動
幅優先探索
１
v1
２
v8
v2
v3
v4
７
v6
６
v5
３
５
v7
４
８
Ｖ４は既に探索済みなので、Ｖ３からｖ５を探索
本日のまとめ
TCP/IPアプリケーション
• 幅優先探索
本日の課題
教科書p.132 図6.7の有向グラフを隣接リストを
用いて作成し、幅優先探索のプログラムを作
成せよ。
実行結果は、各頂点ｖｎが何番目に探索された
のかを表示するようにせよ。
注意）表示法については、教科書には記述がない。自分で考える
こと。（自力で作成するorいろいろ調べる）
ヒントとしては、通過した頂点の番号を配列に記憶させるという方
法がある。
グラフの表現
v1
隣接リスト
v5
v2
ポインタ配列で表現する
v3
v1
v2
v3
v2
v1
v3
v3
v2
v4
v1
v3
v5
v1
v4
v5
v5
v4
v4
ポインタ配列の宣言
vertex *adjlist[5];
レポートの〆切と提出先
レポート提出先：
E2棟（旧システム棟）６F606室（宮島教員室）前
レポートBOX
レポート〆切：
７月28日火曜日 PM５：００頃
今後の予定
７月29日難しい問題とその対応
８月５日確認試験
レポートは本日分を含めて後２回です。

Download Report