圖(Graph)的表示

圖(Graph)

圖，是一種記錄節點和節點之間關連的表示法。對於圖，表示是由集合和集合共同構成的集合，集合中的元素為圖中的節點，故又稱點集合。表示節點和節點之間的邊所構成的集合，每一個邊可以當作純量或是向量，故又稱為邊集合。

圖，可以用兩種方式是表示，一種方法類似前面Hash table中Chaining的表示法，每一個slot中含有一個鏈結串列，這個方法稱為鄰接串列(Adjacency list)表示，另一種方法為使用鄰接矩陣(Adjacency Matrix)來表示。

而節點和節點之間，我們可以根據其走訪的性質，定義他是有向圖(Directed)，還是無向圖(Undirected)，也就是節點和節點之間的邊，是以線段來表示，還是以向量來表示。

對於圖，使用鄰接串列表示法包含有條串列的陣列所構成，陣列中每一個元素中有一條串列。對於每一個屬於集合的節點，包含所有與節點有邊相連的節點，或是可以稱為的鄰居，而鄰接矩陣也是使用差不多的概念，給定一個無向圖，我們可以以下面兩種方式進行表示

在圖(a)中，我們可以知道點集合為, 邊集合，如果在實務上，我們直接使用集合來尋找和1節點有關連的所有節點，我們就必須遍歷整個集合，需要線性時間，因此我們會使用上面提及的鄰接串列法或是鄰接矩陣法來進行處理。

我們可以對鄰接串列表示法做出一點修改，為每一條邊加上權重，那麼，所產生出的圖就是權重圖。我們可以將權重儲存在鏈結串列中的每一個節點當中，當作是一個節點的屬性。而這種表示法具有一些可靠性與安全性在一些系統應用中，像是輸入錯誤或是系統崩潰等等，也具有一定的方便修改性，可以進行一些簡單的修改就讓他支援其他圖的形式與操作。

鄰接串鍊有幾個缺點，那就是我們無法快速的判斷一條邊是否為圖中的邊，且和鄰接矩陣相比，每一個節點需要更多的儲存空間，包含一個整數，和下一個節點位置的指標。

而鄰接矩陣的優點在於矩陣中每一個元素都只需要1 bit就可以表示，只需奧表示有沒有節點就可以了，但是也有一個缺點，當發生很多元素，但卻很少邊的情況，會浪費掉許多空間。

當圖的規模較小時，我們會優先使用鄰接矩陣。

圖的表示

上圖A,B,C等節點，我們會稱為圖的節點或是頂點(Vertex or Node)，節點與節點之間相連的稱為邊，這個範例中，邊是屬於沒有方向的，因此，這是一張無向圖。邊上的數字表示權重。

上面這張圖，如果以鄰接矩陣的方式表示，可以表示成下面這個樣子

int map[5][5]=
{ {0,0,1,1,1}
  {0,0,0,0,1}
  {1,0,0,0,1}
  {1,0,0,0,0}
  {1,1,1,0,0}
};

說明: 以第一行{0,0,1,1,1}為例子，表示0這個節點，和2,3,4節點有存在邊的關係。其實我們可以指細觀察，上面這個二為矩陣其實存在一種對稱關係，以方陣的對角線為對稱軸，這個性質可以使我們使用一些技巧，花費更少的空間，去記住節點和邊之間的關係。

以這個圖為例子，我們可以使用鄰接矩陣，來表示這個具有權重的圖

int map[5][5] =
{ {0,1,6,INT_MAX,INT_MAX}
  {1,0,4,3,1}
  {6,4,0,1,INT_MAX}
  {INT_MAX,3,1,0,1}
  {INT_MAX,1,INT_MAX,1,0}
};

說明: 以第一行{0,1,6,INT_MAX,INT_MAX}為例，表示0這個節點和其他節點之間的權重，如果不存在，則以一個標示符號作為表示。

如果以串列的形式，則為以下

struct edge {
    int id;
    int weight;
    struct node *next;
};
struct map[5]

參考資料:Introduction to algorithms 3rd, 北一女資訊集訓