Graph Theory Chapter 2 An Introduction to Algorithms 大葉大學(Da-Yeh Univ.) 資訊工程系(Dept. CSIE) 黃鈴玲(Lingling Huang)
Outline 2.6 Representing graph in a computer
2.6 Representing graph in a computer ① adjacency matrix: G: v6 v4 v2 v1 v3 v5 1 2 3 4 5 6 1 2 3 4 5 6
② adjacency list: G: 1. 2. 3. 4. 5. 6. v6 v4 v2 v1 v3 v5 2 3 1 3 1 2 4 1 3 1 2 4 5 3 3
② adjacency list: 6 個 點 邊 數 2 neighbor 名稱 neighbor 在表 格中的位置 1. 2. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 表示v1的第一個neighbor位置 7 6 個 點 1. 2 3 ,, v2 ,, 9 ,, v3 ,, 11 2. 1 3 ,, v4 ,, 15 ,, v5 ,, 16 3. 1 2 4 5 ,, v6 ,, 4. 2 表示下一個neighbor位置 8 3 邊 數 2 3 表示沒有了 adjacency list table 5. 3 1 10 3 6. φ 1 12 2 13 4 14 5 3 3
Homework Exercise 2.6: 1