[ 資料結構 小學堂 ] 圖形結構 : 圖形表示法 - 相鄰串列法

前言 : 
這種表示法是以串列結構來表示圖形, 它有點類似相鄰矩陣, 不過忽略掉矩陣中0 的部分, 直接把1 的部分放進節點裡. 如此一來可以有效避免浪費儲存空間. 

相關特性 : 

1. 每一個頂點使用一個串列.
2. 在無向圖中, n 頂點e 邊共需要n 個串列以及 2*e 個節點; 有向圖中則需要n 個串列首節點及e 個節點. 在相鄰串列中計算所有頂點分支度所需的時間複雜度為 O(n+e).

下面討論範例(無向圖)使用串列節點 : 
 

至於相鄰陣列法及相鄰串列表示圖形的優缺點整理如下 : 
 

範例代碼 : 
* ch07.h 代碼 : 

view plaincopy to clipboardprint?

1. #include   
2.   
3. using namespace std;  
4.   
5. /* 
6. * 使用相鄰串列來表式圖形 (P7-12) 
7. */  
8. void ch07_03(bool b);  

* ch07.cpp 代碼 : 

view plaincopy to clipboardprint?

1. #include "ch07.h"  
2.   
3. class graphicPoint{  
4. public:  
5.     int val;  
6.     class graphicPoint *next;  
7.     graphicPoint(){  
8.         next = NULL;  
9.         val = -1;  
10.     }  
11. };  
12.   
13. void ch07_03(bool b) {  
14.     if(b) {  
15.         class graphicPoint head[6];  
16.         int data[14][2] = {{1,2}, {2,1}, {1,5}, {5,1}, {2,3}, {3,2}, {2,4}, {4,2}, {3,4}, {4,3}, {3,5}, {5,3}, {4,5}, {5,4}};  
17.         for(int i=0; i<14; i++) {  
18.             int tmpi = data[i][0];  
19.             int tmpj = data[i][1];  
20.             graphicPoint *npt = new graphicPoint;  
21.             npt->val = tmpj;  
22.             graphicPoint *pt = &head[tmpi];  
23.             while(pt->next != NULL)  
24.                 pt = pt->next;  
25.             pt->next = npt;            
26.         }  
27.   
28.         for(int i=1; i<6; i++) {  
29.             graphicPoint *pt = head[i].next;  
30.             cout << "頂點 " << i << "=>";  
31.             while(pt!=NULL)  {  
32.                 cout << "[" << pt->val << "] ";  
33.                 pt  = pt->next;  
34.             }  
35.             cout << endl;  
36.         }  
37.     }  
38. }  

執行結果 : 

頂點 1=>[2] [5]
頂點 2=>[1] [3] [4]
頂點 3=>[2] [4] [5]
頂點 4=>[2] [3] [5]
頂點 5=>[1] [3] [4]

補充說明 : 
* [ 資料結構 小學堂 ] 鏈結串列 : 單向鏈結串列