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

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

相鄰矩陣法 : 
圖形 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 代碼 :
#include

using namespace std;

/*
 * 圖形表示法 : 相鄰矩陣法 (P7-8)
 */void ch07_01(bool b);

* ch07.cpp 代碼 :
#include "ch07.h"

#define POINT_7_1_COUNT 6
void ch07_01(bool b) {
 int arr[POINT_7_1_COUNT][POINT_7_1_COUNT] = {0}; // 宣告矩陣
 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}};
 for(int i=0; i<14; i++) {
  int tmpi = data[i][0];
  int tmpj = data[i][1];
  arr[tmpi][tmpj] = 1;
 }
 cout << "無向圖形矩陣: " << endl;
 for(int i=1; i<6; i++) {
  for(int j=1; j<6; j++) {
   cout << "[" << arr[i][j] << "] ";
  }
  cout << endl;
 }
}

執行結果 :

無向圖形矩陣:
[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]