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

標籤

2010年10月24日 星期日

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

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

相關特性 : 

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

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

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

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

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

  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]

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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!