Chap5 Graph

圖形(Graph) graph G 包含兩部分 頂點, vertices V(G) 邊edges E(G) G(V,E)表示a graph

Graph 1 2 1 2 1 3 3 4 5 6 G1 2 G2 G3 V(G1)={0,1,2,3} E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} V(G2)={0,1,2,3,4,5,6} E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)} V(G3)={0,1,2} E(G3)={<0,1>,<1,0>,<1,2>}

2 1 3 1 2 (a) 有Cycle圖 Figure 6.3 多重圖 (b)

(b) Some of the subgraph of G3 子圖subgraphs of G1 and G3 1 2 3 1 2 3 G1 (i) (ii) (iii) (iv) (a) Some of the subgraph of G1 1 2 單一 1 分開 (i) (ii) (iii) (iv) (b) Some of the subgraph of G3 2 G3

Connected graph 連通圖 1 2 1 2 3 3 4 5 6 G1 G2 tree

Degree degree分支度:附著在頂點的邊數 in-degree 內分支度 out-degree 外分支度 頂點V的內分支度是指以V為終點(即箭頭指向V)的邊數 out-degree 外分支度 頂點V的外分支度是指以V為起點的邊數

1 2 1 2 3 4 5 6 3 G1 G2 1 2 G3 undirected graph無向圖 degree 3 2 3 3 3 3 2 1 2 3 1 2 3 3 3 3 4 5 6 3 3 G1 1 1 G2 1 1 in:1, out: 1 directed graph有向圖 in-degree out-degree 1 in: 1, out: 2 2 in: 1, out: 0 G3

Graph表示法 Adjacency Matrix 相鄰矩陣 Adjacency Lists 相鄰串列

Adjacency Matrix 1 2 3 4 5 6 7 1 2 3 1 2 G2 G1 symmetric G4

Data Structures for Adjacency Lists #define MAX_VERTICES 50 typedef struct node *node_pointer; typedef struct node { int vertex; struct node *link; }; node_pointer graph[MAX_VERTICES]; int n=0; /* vertices currently in use */

1 2 3 4 5 6 7 1 2 3 1 2 3 1 2 3 1 2 3 4 5 6 7 1 2 2 3 3 1 3 3 1 2 1 2 5 G1 4 6 1 2 1 5 7 2 1 6 G4 G3 2

Graph的基本運作 Traversal拜訪 Spanning Trees生成樹 Depth First Search (DFS)縱向優先搜尋 preorder tree traversal Breadth First Search (BFS) 橫向優先搜尋 level order tree traversal Spanning Trees生成樹

depth first search: v0, v1, v3, v7, v4, v5, v2, v6 breadth first search: v0, v1, v2, v3, v4, v5, v6, v7

Spanning Trees生成樹 Spanning Tree: 以最少的邊數, 來連接圖形中所有的頂點, 且不能有迴圈(Cycle) |E| = |V| -1 (邊數 = 頂點數 -1) Kruskal’s Algorithm 將所有的邊由小到大排列, 依序加入最小的邊, 但不可以造成迴路(Cycle) Prim’s Algorithm 每次向外長出目前最小的邊,有走一步算一步的味道, 但不可以造成迴路(Cycle)

Spanning Tree生成樹 1 2 1 2 1 2 1 2 3 3 3 3 G1

DFS vs BFS Spanning Tree 1 2 1 2 1 2 3 4 5 6 3 4 5 6 3 4 5 6 7 7 7 DFS Spanning BFS Spanning

Kruskal’s Algorithm 0 5 2 3 1 6 1 2 3 6 3 4 4 6 4 5 0 1 10 12 14 1 2 3 4 5 6 1 2 3 4 5 6 28 16 1 10 10 14 16 18 5 6 2 24 25 22 18 12 4 22 24 3 25 6/9 28

0 5 2 3 1 6 1 2 3 6 3 4 4 6 4 5 0 1 10 12 14 16 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 10 10 10 18 14 14 16 22 12 12 12 24 25 28 + 3 6 cycle

0 5 2 3 1 6 1 2 3 6 3 4 4 6 4 5 0 1 10 12 14 1 2 3 4 5 6 1 2 3 4 5 6 16 10 10 18 14 16 14 16 22 25 12 12 24 22 22 + 4 6 25 cycle cost = 10 +25+22+12+16+14 28

Prim’s Algorithm 28 10 1 14 16 5 6 2 24 25 18 1 2 3 4 5 6 12 1 2 3 4 5 6 4 1 22 3 10 10 10 5 6 2 25 25 4 22 3

28 10 1 14 16 5 6 2 24 25 18 12 4 22 3 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 10 10 10 16 14 16 25 25 25 12 12 12 22 22 22

The Shortest Path最短路徑 4 3 2 1 5 7 6 Cost adjacency matrix Boston 1500 Chicago San Francisco Denver 250 1200 3 800 1000 1 2 New York 5 300 1000 1400 New Orleans 1700 900 7 1000 Los Angeles 6 Miami 0 1 2 3 4 5 6 7 0 0 1 300 0 2 1000 800 0 3 1200 0 4 1500 0 250 5 1000 0 900 1400 6 0 1000 7 1700 0 Cost adjacency matrix

(a) (b) (c) 4 1500 4 1500 4 250 3 3 5 250 250 5 1000 5 900 6 選5 4到6由改成1250 4到3由1500改成1250 4 4 4 (d) (f) (e) 3 250 250 250 1000 5 5 7 5 7 1400 7 1400 1400 900 900 6 1000 6 4到7由改成1650 選6 4-5-6-7比4-5-7長

(g) (h) 4 4 3 1200 2 3 250 250 1000 5 1000 5 7 1400 7 1400 900 900 6 6 選3 4到2由改成2450 (i) 4 4 1200 (j) 2 3 250 250 1000 5 5 7 1400 7 1400 900 6 4到0由改成3350 選7

Example for the Shortest Path