[ 資料結構 小學堂 ] 圖形結構 : 圖形表示法

前言 : 
知道了圖形的各種定義與觀念後, 進一步了解有關圖形的表示法就益顯重要了. 圖形一共有四種表示法, 將分別描述如下. 

相鄰矩陣法 : 
圖形 A有 n 個頂點, 以 nXn 的二維矩陣表示. 此矩陣定義如下 : 

對於一個圖形 G=(V,E), 假設有 n 個頂點, n>=1, 則可以將 n 個頂點的圖形, 利用一個 nXn的二維矩陣來表示, 其中假設A(i,j)=1, 則表示圖形中有一條邊(Vi, Vj) 存在. 反之A(i,j)=0, 則表示沒有一條邊存在.

相關特性說明如下 : 

1. 對於無向圖形而言, 相鄰矩陣一定是對稱的, 而且對角線一定為0. 有向圖形則不一定是如此.
2. 在無向圖形中, 任一節點i 的分支度為第i 列所有元素的合. 在有向圖形中, 節點i 的出分支度為第i 列所有元素合, 而入分支度為第i 行所有元素合.
3. 用相鄰矩陣法表示圖形共需要 n^2 空間, 由於無向圖形的相鄰矩陣一定是具有對稱關係, 所以扣除對角線全部為零外, 僅需要儲存上三角形或下三角形的資料即可, 因此僅需 n(n-1)/2 空間.

接著就實際來看一個例子, 請參考下圖 : 
 
由於上圖共有五個頂點, 故使用 5x5 的二維矩陣存放圖形. 在參考第一列時, 因為頂點1 與 頂點2, 5有邊連接, 故在第一列的第2行與第5行分別為1. 並以此類推. 

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

view plaincopy to clipboardprint?

1. #include   
2.   
3. using namespace std;  
4.   
5. /* 
6. * 圖形表示法 : 相鄰矩陣法 (P7-8) 
7. */  
8. void ch07_01(bool b);  

* ch07.cpp 代碼 : 

view plaincopy to clipboardprint?

1. #include "ch07.h"  
2.   
3. #define POINT_7_1_COUNT 6  
4. void ch07_01(bool b) {  
5.     int arr[POINT_7_1_COUNT][POINT_7_1_COUNT] = {0}; // 宣告矩陣  
6.     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}};  
7.     for(int i=0; i<14; i++) {  
8.         int tmpi = data[i][0];  
9.         int tmpj = data[i][1];  
10.         arr[tmpi][tmpj] = 1;  
11.     }  
12.     cout << "無向圖形矩陣: " << endl;  
13.     for(int i=1; i<6; i++) {  
14.         for(int j=1; j<6; j++) {  
15.             cout << "[" << arr[i][j] << "] ";  
16.         }  
17.         cout << endl;  
18.     }  
19. }  

執行結果 : 

無向圖形矩陣:
[0] [1] [0] [0] [1]
[1] [0] [1] [1] [0]
[0] [1] [0] [1] [1]
[0] [1] [1] [0] [1]
[1] [0] [1] [1] [0]

補充說明 : 
* [ 資料結構 小學堂 ] 圖形結構 : 圖形介紹