--- # System prepended metadata title: 資料結構 第六章 圖形 tags: [資料結構] --- --- tags: 資料結構 --- # 資料結構 第六章 圖形 ![](https://i.imgur.com/Vr4nDco.jpg) ## 一、圖形介紹 ### (一)七橋問題 ![](https://i.imgur.com/dY8dCX6.jpg) 討論四個島嶼七座橋(將所有邊走過一次不重複)，將島嶼表示為頂點橋表示為邊，【參考離散數學】尤拉推導每個點degree(分支)需要皆為偶數，否則無法完成，或是(2點degree為奇數其餘為偶數) ### (二)圖形分別 #### 1、有向圖與無向圖 ![](https://i.imgur.com/7JxEaBi.jpg) ##### G~1~、G~2~為無向圖(0→1，1→0相同)，G~3~為有向圖(0→1，1→0不同) #### 2、簡單圖與多重圖 ![](https://i.imgur.com/ktOYTva.jpg) ##### G=:圖形若G中任二點之間至多一邊相連，稱G為simple graph，否則稱G為mutigraph ### (三)子圖 #### 1、定義:G=,則S為G的subgraph表示S = ,其中V'屬於V,E'屬於E #### 2、圖示 ![](https://i.imgur.com/e9MDe5D.jpg) ### (四)連通圖 #### 1、連通:無向圖中任兩點都有路經可以到達 #### 2、連通元件:圖形中內的圖形(元件、部分)為連通 ![](https://i.imgur.com/AjeypUS.jpg) #### 3、強連通:有向圖中任兩點都有路經可以到達 #### 4、強連通元件:圖形中內的圖形(元件)皆為強連通【以圖G~3~為例】 ![](https://i.imgur.com/48i58Ns.jpg) ### (五)圖形資料抽象型態 【變數設定】for all graph belong to Graph, v1, v2, and v3 belong to Vertices (1)Graph Create():創造一個空圖 (2)Graph InsertVertex(graph, v1, v2):將點V插入圖形中點(indegree=0) (3)Graph InsertEdge(graph, v1, v2):加入一個邊在v1,v2之間 (4)Graph DeleteVertex(graph, v):刪除一個點與連接在點上的所有邊。 (5)Graph DeleteEdge(graph, v1, V2) (6)Boolean isEmpty(graph):前提假設圖等於空回傳True，前提假設不成立則回傳False (7)List Adjacent(graph, v):回傳所有與V點相連的所有頂點。 ### (六)圖形表示方法 #### 以下圖為例 ![](https://i.imgur.com/EkSl2xg.jpg) ![](https://i.imgur.com/GzsQgBr.jpg) #### 1、相鄰矩陣 x,y軸為各點有邊相連的話則為1(N個點則需準備N^2個位置) ![](https://i.imgur.com/6gml9gy.jpg) #### 2、相鄰串列 準備一個陣列(n點準備N格)，每個點若有邊相鄰則連結1個Link至該點 ![](https://i.imgur.com/mZMneMe.jpg) #### 3、相鄰多重串列 ##### (1)節點結構 ![](https://i.imgur.com/YAHuNZ9.jpg) ##### (2)以G~1~為例 ###### 邊名稱 邊的左右2點 討論左點其他連結的邊 討論右點其他連結的邊 ![](https://i.imgur.com/hx80qIa.jpg) ### 二、圖形操作 #### (一)深度搜尋 ##### 1、程式碼 【類似迷宮走錯退回原位，故使用Stack】 void dfs(int v) { node_pointer w; visited[v] = True; printf("%5d",v); for (w = graph[v]; w; w = w ->link) if(!visited[w->vertex]) dfs(w->vertex); } ##### 2、時間複雜度分析 ###### (1)若使用adjacency lists 則需走訪O(2*e)經過所有點(2為常數)，故時間複雜度為O(e) ###### (2)若使用adjacency matrix 則需走訪(n^2^)格個儲存格，故時間複雜度為O(n^2^) ##### 3、圖例: ![](https://i.imgur.com/0DPF1td.jpg) ##### DFS走訪: (1) V~0~，V~1~，V~3~，V~7~，V~4~，V~5~，V~2~，V~6~ (2) V~0~，V~2~，V~5~，V~7~，V~4~，V~1~，V~3~，V~6~ (3) V~0~，V~1~，V~4~，V~7~，V~5~，V~2~，V~6~，V~3~ ...etc (不唯一) #### (二)廣度搜尋 ##### 1、程式碼 【廣度搜尋以鄰近相連點優先，故使用Queue，先進先出概念，優先拜訪相鄰點】 void bfs(int v) { node_pointer w; queue_pointer front,rear; front = rear = NULL; printf("%5d",v); visited[v] = True; addq(&front, &rear, v); while (front) { V = deleteq(&front); for (w = graph[v]; w; w = w->link) if (!visited[w->vertex]) { printf("%5d", w->vertex); addq(&front,&rear,W->vertex); visited[w->vertex] = true; } ) } ##### 2、時間複雜度分析 ###### (1)若使用adjacency lists: 每個點都會進入Queue(佇列一次)每次delete都會走訪該點的邊，將邊連有連到的頂點插入佇列中 每個點都走訪連至的邊(2E = degree和)，故時間複雜度為O(2*E)，(2為常數)故為O(E) ###### (2)若使用adjacency matrix: 則需走訪所有儲存空間(n^2^)，故時間複雜度為O(n^2^) ##### 3、圖例: ![](https://i.imgur.com/0DPF1td.jpg) ##### BFS走訪: (1) V~0~，V~1~，V~2~，V~3~，V~4~，V~5~，V~6~，V~7~ (2) V~0~，V~2~，V~1~，V~5~，V~6~，V~3~，V~4~，V~7~ (3) V~0~，V~1~，V~4~，V~3~，V~2~，V~6~，V~5~，V~7~ ...etc (不唯一) ##### (三)連通元件 ###### 1、使用DFS or BFS ###### 依G~4~為例為2個連通圖但2圖不相連，故使用BFS or DFS 無法一次拜訪完所有的點，利用此特性，來確認此圖有幾個連通元件。 ###### 2、程式碼 void connected (void) { int i; for (i = 0;, i < n; i++) if(!visited[i]) { dfs(i); printf("\n"); } } ##### 3、時間複雜度分析 ###### (1)adjacency lists: 利用DFS需要O(e)的時間，使用迴圈走訪每個點O(n)，故找到所有連通元件需要O(n+e) ###### (2)adjacency matrix: 確認連接的組件需要O(n^2) ##### (四)生成樹 ###### 1、圖示(n=4為例) ![](https://i.imgur.com/GssOyBD.jpg) //Tree不含cycle，邊數 = 頂點數-1 ![](https://i.imgur.com/Z6eSS68.jpg) 以深度搜尋創造的生成樹稱為深度生成樹 以廣度搜尋創造的生成樹稱為廣度生成樹 ###### 2、圖示(深、廣度生成樹) ![](https://i.imgur.com/1B3FpfA.jpg) 與BFS和DFS一樣不唯一 ##### (五)雙向連接元件與樞紐點 ##### 1、樞紐點(Articulation Points) 此點若刪除後導致原圖不連通(變成2個(含)以上的連通元件)，此點稱之樞紐點。 ##### 2、雙向連通圖(Biconnected Graph) 途中不含任何樞紐點(EX:cycle) ##### 3、雙向連通元件(Biconnected Components) 圖形中最大的雙聯通圖形 ##### 4、圖示: ![](https://i.imgur.com/B4JEugY.jpg) ##### 5、DFS生成樹 dfn(3)=0 【3為起點】 DFS: 3、4、2、1、0、5、6、7、9、8 ##### 6、圖示 ![](https://i.imgur.com/dVVsBcr.jpg) ##### 7、邊的特性 【定義】 未被訪過的點:白色 被拜訪過的點:灰色 已無法再拜訪:黑色 | 邊名稱 | back edge | Tree edge | forward edge | cross edge | |:------:|:-------------:|:-------------:|:-------------:|:-------------:| | 特性 | 灰色點→灰色點 | 灰色點→白色點 | 灰色點→黑色點 | 灰色點→黑色點 | | 無向圖 | 有 | 有 | 沒有 | 沒有 | | 有向圖 | 有 | 有 | 有 | 有 | ##### //forward edge & cross edge 要區別以發現拜訪時間判斷 ##### 8、dfn & low ###### (1)dfn:計算出每個點被追蹤的順序(ex: dfn(a)=3 > dfn(b)=4 故a比b先追蹤) ###### (2)low:計算出此點的子樹沿著backedge所能到達的祖先，最小的dfn值 ![](https://i.imgur.com/RcEgxZ6.jpg) ###### (3)程式碼: void dfnlow(int u, int v) { node_pinter ptr; int w; dfn[u]=low[u] = num++; for(ptr = graph[u]; ptr; ptr = ptr->link) { w= ptr->vertex; if(dfn[w]<0) { dfnlow(w,u); low[u] = MIN2(low[u],low[w]); } else if(w != V) low[u] = MIN2(low[u],dfn[w]); } } ##### 9、找出雙連通元件 先判斷樞紐點則可以找到所有雙連通元件 ###### 程式碼: void bicon(int u, int v) { node_pointer ptr; int x,y,z; dfn[u] = low[u] =num++; for(ptr = graph[u]; ptr; ptr = ptr->link) { w= ptr->vertex; if (v != w && dfn[w] < dfn[u]) add(&top,u,w); if(dfn[w]<0) { bicon(w,u); low[u] = MIN2(low[u],low[w]); if (low[w] >= dfn[u]) { printf("New biconnected component:"); do { delete(&top, &x, &y); printf("<%d,%d>,x,y"); } while(!((x == u) && (y ==w))); printf("\n"); } } else if (w != v) low[u] =MIN2(low[u],dfn[w]); } } ###### (1)樹根若有2個或以上的子點 ###### (2)頂點u非樹根，頂點存在子點v，滿足LOW(v)≧DFN(u)時，頂點u為樞紐點。 ### 三、最小成本生成樹(Minmim cost panning trees) 找出最小成本生成樹最常見的3種演算法(Kruskal’s Algo、Prim’s Algo、Soilin’s Algo)，皆為貪婪演算法。 【定義】 1.權重在於邊上 2.使用貪婪演算法(故邊數取最少): 邊數 = 點數-1 3.為樹的型態不含有cycle #### (一)Kruskal’s Algorithm ##### 1、步驟: step1:將權重最小的邊加入 step2:檢查是否產生cycle step3:直到加入n-1條邊結束 ##### 2、圖示: ![](https://i.imgur.com/4ySMtqU.jpg) ##### 3、程式碼: T = {}; while (T contains less than n-1 edges && E is not empty) { choose a least cost edge (v,w) from E; delete (v,w) from E; if ((v,w) does not create a cycle in T) add (v,w) to T; else discard (v,w); } if (T contains fewer than n-1 edges) printf("No spanning tree\n"); #### (二)Prim’s Algorithm ##### 1、步驟: step1:每次加入一個點至新的集合 step2:找出最小權重的邊加入新的集合 step3:直到新集合內蒐集滿所有點即完成 ##### 2、圖示: ![](https://i.imgur.com/9Ehp0uG.jpg) ##### 3、程式碼: T ={}; TV = {0}; while (T contains fewer than n-1 edges) { let (u, v) be a least cost edge such that u belong to TV and V not belong to TV; if (there is no such edge) break; add v to TV; add (u, v) to T; } if (T contains fewer than n-1 edges) printf("No spanning tree\n"); #### (三)Soilin’s Algorithm ##### 1、步驟: step1:視每個點為一個森林 step2:加入每個權重最小的邊，使森林串聯起來(並檢查是否產生cycle) step3:串聯到只剩一個樹即完成 ##### 2、圖示: ![](https://i.imgur.com/BalP8sD.jpg) ### 四、最短路徑 #### (一)單一點至所有點的距離(Single Source All Destinations) ![](https://i.imgur.com/ZU54WsN.jpg) ##### 1、Dijkstra's algo 由最近的點開始，依序找出每個點的最短路徑【不允許負邊】【不允許負環】 --- step1: 假設a -> j 路徑長度為10 【2種可能】 【可能一】: 加入新點u, a -> j　仍為最短路徑 【可能二】: 加入新點u, a -> j > a->u->j ,則取代最短路徑 step2: 直到所有點都加入後,即可獲得從a -> j的最短路徑 ##### 2、Bellmen's algo 討論起終點最短距離，中間經過1個點、2個點至n-1個點【允許負邊】【不允許負環】 --- step1: 假設a -> j 中間經過1~n-1個點，路徑長度為10 【2種可能】 step2: 選出最短路徑 #### (二)所有點至其他點的距離(All Pairs Shortest Paths) ##### 1、Floyd-Warshall 求任兩點的最短距離【允許負邊】【不允許負環】 將頂點編號討論起終點距離（經過V1、V2....Vn）的距離，選最短路徑 --- step1: 將所有點編號(假設有n個點) step2: 討論假設a -> j pass1:可經過V1 最短距離。 pass2:可經過V1、V2最短距離。 ... pass(n-2):可經過V1....Vn-2最短距離。 step3:討論完可經過所有點即為最短距離 ##### 2、Johnson's algo 在圖中多加入一個點連至所有點權重為０【允許負邊】【不允許負環】 在使用bellmen'algo，無負邊也可使用Dijkstra's algo //稀疏矩陣中效果比Floyd-warshall好 O(V*E+V^2logV) #### (三)遞移包(Transitive Closure) ##### 1、A^+^、A^*^圖示: ![](https://i.imgur.com/UqauMjW.jpg) ###### A^*^ = A^+^ U I ### 五、網絡與拓樸排序 #### (一)點為活動之網絡AOV(Activity On Vertex Networks) ##### 1、定義: 有向圖G其中頂點表示任務或活動，而邊表示任務之間的優先級關係。 ##### 2、圖示及表示: ![](https://i.imgur.com/cZRSenR.jpg) ![](https://i.imgur.com/gHoT3H2.jpg) ##### 3、拓樸排序: ![](https://i.imgur.com/74rm0ZJ.jpg) #### (二)邊為活動之網絡AOE(Activity On Edge (AOE) Networks) ##### 1、條件 (1)邊代表活動且不能有迴圈 (2)單一起終點 ##### 2、圖例及表示 ![](https://i.imgur.com/Am0DGOv.jpg) ![](https://i.imgur.com/i5Rqtyq.jpg) ##### 3、臨界活動 活動最早開始時間與最晚開始時間一樣的話為關鍵(臨界)活動 關鍵路徑上的所有活動都是關鍵活動，提前完成非關鍵活動（不在關鍵路徑的活動）並不能加快工程的進度。 ![](https://i.imgur.com/9UwfhAl.jpg) > 參考資料:Fundamentals of Data Structures in C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed