北一女中 資訊選手培訓營 圖論基礎 By Nan(2012.07.08 )
圖論，到底是什麼呢？
圖論最常出現的形式： 點(Vertex or Node) 邊(Edge) 兩種在程式裡表示的方式： 鄰接矩陣跟鄰接串列 權重(Weight) <無向邊vs. 有向邊> 權重(Weight) 兩種在程式裡表示的方式： 鄰接矩陣跟鄰接串列
鄰接矩陣 [0] [1] [2] [3] [4] 1 map 無權重無向邊 int map[5][5] = 1 無權重無向邊 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] [1] [2] [3] [4] 1 6 INF 4 3 map 有權重無向邊 #define INF 2147483647 1 6 INF 4 3 有權重無向邊 #define INF 2147483647 int map[5][5] = { {0, 1, 6, INF, INF}, {1, 0, 4, 3, 1}, {6, 4, 0, 1, INF}, {INF, 3, 1, 0, 1}, {INF, 1, INF, 1, 0} };
鄰接矩陣 無權重有向邊 有權重有向邊 [0] [1] [2] [3] [4] 1 [0] [1] [2] [3] [4] 2 INF 1 5 map [0] [1] [2] [3] [4] 1 有權重有向邊 map [0] [1] [2] [3] [4] 2 INF 1 5 6 3
鄰接串列 2 3 4 1 [0] [1] [2] [3] [4] map 無權重無向邊 struct node * map[5]; 1 無權重無向邊 struct node { int id; struct node *next; }; struct node * map[5];
鄰接串列 [0] [1] [2] [3] [4] map 1/1 2/6 0/6 1/4 0/1 1/3 3/1 2/4 3/3 4/1 2/1 有權重無向邊 struct edge { int id; int weight; struct edge *next; }; struct edge* map[5];
鄰接串列 無權重有向邊 基本上跟無向的很像， 只是只會有一個方向有邊。 所以…換你畫囉~~ 有權重有向邊
補充：串接的方式 #include <stdlib.h> #define NEW(T, N) (T)malloc((N) * sizeof(T) ) struct edge { int id; int weight; struct edge *next; }; int main(){ struct edge *map[5]; struct edge *ptr = 0; ptr = NEW(struct edge, 1); ptr->id = 1; ptr->weight = 1; ptr->next = NULL; map[0] = ptr; ptr->id = 2; ptr->weight = 6; map[0]->next = ptr; //… }
你暈了嗎？ 別擔心，我們目前比較常用的是鄰接矩陣的做法。 但真正在寫軟體什麼的話，是要用鄰接串列喔！