Presentation is loading. Please wait.

# 101北一女中 資訊選手培訓營 圖論基礎 2012.07.08 Nan.

## Presentation on theme: "101北一女中 資訊選手培訓營 圖論基礎 2012.07.08 Nan."— Presentation transcript:

101北一女中 資訊選手培訓營 圖論基礎 Nan

<無向邊vs. 有向邊> 權重(Weight) 兩種在程式裡表示的方式： 鄰接矩陣跟鄰接串列

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} };

1 6 INF 4 3 有權重無向邊 #define INF 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} };

map [0] [1] [2] [3] [4] 1 有權重有向邊 map [0] [1] [2] [3] [4] 2 INF 1 5 6 3

1 無權重無向邊 struct node { int id; struct node *next; }; struct node * map[5];

2/1 有權重無向邊 struct edge { int id; int weight; struct edge *next; }; struct edge* map[5];

#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; //… }

Download ppt "101北一女中 資訊選手培訓營 圖論基礎 2012.07.08 Nan."

Similar presentations

Ads by Google