Ibaraki Univ. Dept of Electrical & Electronic Eng.

Presentation on theme: "Ibaraki Univ. Dept of Electrical & Electronic Eng."— Presentation transcript:

1 Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズムとデータ構造 Ibaraki Univ. Dept of Electrical & Electronic Eng. Keiichi MIYAJIMA

2 深さ優先探索

3 深さ優先探索 v1 v8 v2 v7 v6 v3 v4 v5 図のような無向グラフをどのように探索するか？

4 深さ優先探索 １ v1 v8 v2 v7 v6 v3 v4 v5 V1からスタートすると・・・

5 深さ優先探索 １ v1 ２ v8 v2 v7 v6 v3 v4 v5 まずV2を探索

6 深さ優先探索 １ v1 ２ v8 v2 ３ v7 v6 v3 v4 v5 次にV3を探索

7 深さ優先探索 １ v1 ２ v8 v2 ３ v7 v6 v3 v4 v5 ４ 次にV４を探索

8 深さ優先探索 １ v1 ２ v8 v2 ３ v7 v6 v3 v4 v5 ４ V２は既に探索しているので、いったんｖ３にもどって・・・

9 深さ優先探索 １ v1 ２ v8 v2 ３ v7 v6 v3 v4 v5 ５ ４ V５を探索

10 深さ優先探索 １ v1 ２ v8 v2 ３ v7 v6 v3 v4 v5 ５ ４ V５は行き止まりなので、ｖ３に戻り、さらにｖ２までもどり・・・

11 深さ優先探索 １ v1 ２ v8 v2 ３ v7 v6 v3 ６ v4 v5 ５ ４ Ｖ４はすでに探索済みなので、V６を探索

12 深さ優先探索 １ v1 ２ v8 v2 ３ v7 v6 v3 ６ v4 v5 ５ ４ Ｖ６からｖ１は既に探索済みなので、いったんｖ２に戻り、さらにｖ１へ戻る

13 深さ優先探索 １ v1 ２ v8 v2 ３ v7 v6 v3 ６ ７ v4 v5 ５ ４ Ｖ７を探索

14 深さ優先探索 １ v1 ２ v8 v2 ８ ３ v7 v6 v3 ６ ７ v4 v5 ５ ４ 「深さ優先」なのでｖ１に戻らずに、ｖ８を探索

15 深さ優先探索 １ v1 ２ v8 v2 ８ ３ v7 v6 v3 ６ ７ v4 v5 ５ ４ 全ての頂点を探索し終わったら終了

16 本日のまとめ TCP/IPアプリケーション 　深さ優先探索

17 本日の課題 教科書p.132 図6.7の有向グラフを隣接リストを用いて作成し、深さ優先探索のプログラムを作成せよ。
実行結果は、各頂点ｖｎが何番目に探索されたのかを表示するようにせよ。 注意）　表示法については、教科書には記述がない。自分で考えること。（自力で作成するorいろいろ調べる） ヒントとしては、通過した頂点の番号をそのまま表示させていくという方法がある。

18 グラフの表現 v2 v1 v5 v3 v4 隣接リスト ポインタ配列で表現する ポインタ配列の宣言 vertex *adjlist[5];

19 レポートの〆切と提出先 レポート提出先： E2棟（旧システム棟）６F606室（宮島教員室）前 レポートBOX レポート〆切：
７月２１日火曜日　PM５：００頃

20 今後の予定 ７月２２日　幅優先探索 ７月２９日　難しい問題とその対応 ８月５日　確認試験 レポートは本日分を含めて後３回です。