ｽﾗｲﾄﾞﾀｲﾄﾙなし

2015. 7. 7
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Keiichi MIYAJIMA
グラフとネットワーク
グラフの表現
v1
v5
v2
v3
v4
図のような有向グラフをどうやって表現するか？
グラフの表現
v1
v5
v2
v3
隣接行列
隣接リスト
v4
グラフの表現
隣接行列
v1
v5
v2
v3
v1
v2
v3
v4
v5
v1 v 2
0 0
1 0

0 0

0 0
1 0
v3 v 4 v5
1 0 0

1 0 0
0 1 0

0 0 0
0 1 0
v4
グラフの表現
v1
隣接リスト
v5
v2
v3
v1
v3
v2
v1
v3
v4
v4
null
v1
v5
v3
v4
v4
グラフの表現
v1
5
7
v2
v5
4
3
3
v3
2
v4
図のような有向グラフに「重み」がある場合
グラフの表現
重み付き隣接行列
7
v2
4
3
v3
v1
v2
v3
v4
v5
5
v5
3
v1 v 2
0 0
7 0

0 0

0 0
5 0
v1
v3 v 4 v5
4 0 0

3 0 0
0 2 0

0 0 0
0 3 0
2
v4
グラフの表現
重み付き隣接リスト
7
4
3
3
v3
v3 4
v2
v1 7
v3 3
v3
v4 2
null
v1 5
v4 3
v4
v5
5
v5
v2
v1
v1
2
v4
グラフの表現
v1
v2
v5
v3
v6
図のような「根付き木」の場合
v4
v7
v8
v9
グラフの表現
図のような隣接リストの改良
root
v1
null
v2
v3
v4
null
v5
v6
null
・・・
null
null
本日のまとめ
TCP/IPアプリケーション
• グラフの表現
•隣接行列
•連結リスト
•根付き木の表現
本日やるべきこと
教科書第6章p.123～128を読んで、隣接リスト
によるグラフ構造をプログラムできるようにして
おくこと。
リスト構造については、p.25～31を復習しておくこと。
今日のプログラムは今後の課題（次回は「深さ優先探索」、その次
は「幅優先探索」）の前哨なので、提出の必要はない。

Download Report