圖形結構 Graph Structure chapter 9 德明科技大學資訊科技系.

Presentation on theme: "圖形結構 Graph Structure chapter 9 德明科技大學資訊科技系."— Presentation transcript:

1 圖形結構 Graph Structure chapter 9 德明科技大學資訊科技系

2 圖形理論的起源 「肯尼茲堡橋樑」問題 由某地點出發，最後再回到原出發點，必須要經過每一座橋，並且只能經過一次 德明科技大學資訊科技系

3 數學家尤拉（Eular）使用的方法 利用頂點（Vertices）來表示每塊土地，邊（Edge）代表每一座橋樑
如果每個頂點的分支度皆為偶數時，才能從某一個頂點出發，經過每一個邊後，再回到出發的頂點 德明科技大學資訊科技系

4 圖形 Graph 無向圖形(Undirected Graph) 有向圖形(Directed Graph)
由頂點(Vertices)和邊(Edges)所組成 以G=(V,E)來表示 V為所有頂點的集合，E為所有邊的集合 無向圖形(Undirected Graph) 邊(Edges)是沒有方向性的 邊(V1,V2)與邊(V2,V1)是相同的 有向圖形(Directed Graph) 邊(Edges)是有方向性的 邊<V1,V2>與邊<V2,V1>是不相同的 德明科技大學資訊科技系

5 【舉例】 圖(A)是 無向圖形中，頂點(Vertices)和邊(Edges) 如下：
V(G)={A,B,C,D,E} E(G)={(A,B),(A,C),(B,A),(B,D),(C,A),(C,E),(D,B) ,(D,E) ,(E,C) ,(E,D)} 圖(B)是 有向圖形中，頂點(Vertices)和邊(Edges) 如下： E(G)={<A,B>,<A,C>,<B,D>,<C,E>,<D,E>} 德明科技大學資訊科技系

6 圖形結構中常用的專有名詞 完整圖形 ( complete graph )
在「無向圖形」中，若有n個頂點，並且恰好有n(n-1)/2個邊，稱為「完整圖形」。 在「有向圖形」中，若有n個頂點，並且恰好有n(n-1)個邊，稱為「完整圖形」 德明科技大學資訊科技系

7 路徑 ( path ) 簡單路徑(simple path) 在圖形，相異兩點間所經過的邊稱為路徑
如圖(A)中，A到E的路徑有{(A,B), (B,E)}、{(A,C), (C,E)}及{(A,B),(B,D),(D,E)}等 簡單路徑(simple path) 路徑不會有循環(cycle，又稱迴圈) {(A,B),(B,D),(D,E),(E,C),(C,A)}起點及終點都是A，所以是一個循環路徑。 德明科技大學資訊科技系

8 路徑長度(Path Length) 子圖(subgraph) 路徑長度 k 代表路徑上的邊(Edge)的數量
若 G’=(V’,E’) 是 G=(V,E) 的子圖， 則V’V與E’E 德明科技大學資訊科技系

9 連通圖形(Connected Graph)
在無向圖形中，若頂點Vi到頂點Vj間存在路徑，則Vi和Vj是相連的 連通圖形(Connected Graph) 如果圖形G中，任兩個頂點均為相連，則此圖形稱為相連圖形，否則稱為非相連圖形 連通單元(Connected Component) 圖中最大的連通子圖（Maximal Connected Subgraph），下圖可以視為2個連通單元 德明科技大學資訊科技系

10 緊密連通(Strongly Connected)
有相向圖形(Directed Graph)之中，任一個頂點<Vi,Vj> 之間都有一條從 Vi 到 Vj 的路徑並且也有一條從Vj到 Vi的路徑(Directed Graph) 相鄰(Adjacent) 兩個頂點 u,vV，(u,v)E，稱頂點 u 與頂點 v 相鄰 兩個頂點有邊直接相連 德明科技大學資訊科技系

11 分支度(Degree) 無向圖：頂點 u 的分支度=附著於 u 的邊的總數，如圖9-3之圖(A)中A頂點的分支度為2 有向圖G=(V,E)
入分支度 ( in - degree )：指某一個頂點v擁有「進入」的邊數。如圖9-3之圖(B)中，A 頂點的入分支度為0，而E頂點的入分支度為2 出分支度 ( out - degree )：剛好和入分支度相反，指的是某一頂點v擁有「出去」的邊數。如圖9-3之圖(B)中，A頂點的出分支度為2，而E頂點的出分支度為0 德明科技大學資訊科技系

12 圖形的表示法 圖形的表示法有四種常見的方式 相鄰矩陣(Adjacency Matrix) 相鄰串列(Adjacency Lists)
相鄰多元串列(Adjacency Multi lists) 索引表格(Indexed Table) 德明科技大學資訊科技系

13 相鄰矩陣 若圖形G = ( V , E ) 、|V|=n、 n >= 1 具有 n 個頂點
我們可以利用一個 n × n 的二維陣列來表示圖形G ，稱其為相鄰矩陣 ( adjacency matrix ) 德明科技大學資訊科技系 無向圖形中的相鄰矩陣就是一種對稱矩陣

14 相鄰矩陣 特性 矩陣A[i][j] = 0 表示邊E(i,j)不存在 矩陣A[i][j] = 1 表示邊E(i,j)存在
無向圖的相鄰矩陣以對角線對稱，A[i][j]=A[i][j] 德明科技大學資訊科技系

15 無向圖 有向圖 德明科技大學資訊科技系

16 相鄰串列 若圖形G = ( V , E ) 、|V|=n、 n >= 1 具有 n 個頂點，使用n個鏈結串列來存放圖形
每個鏈結串列分別代表一個頂點及其相鄰的頂點 無向圖 德明科技大學資訊科技系

17 相鄰串列 有向圖 德明科技大學資訊科技系

18 加權圖形 在圖形中的邊(E)可以附帶數字(稱為權重)以描述相關的資訊 以相鄰矩陣時表示加權圖形時，矩陣內的數值就不是只有0與1，而是
例如兩個都市之間的距離 以相鄰矩陣時表示加權圖形時，矩陣內的數值就不是只有0與1，而是 0: 代表沒有邊連接兩個頂點 權重數值 德明科技大學資訊科技系

19 圖形的走訪 和樹的走訪(traversal)相同，圖形的走訪條件是 圖形走訪主要有兩種做法 每個節點都會被拜訪 每個節點都只會走到一次
深度優先搜尋 Depth-First-Search，DFS 廣度優先搜尋 Breadth-First-Search，BFS 德明科技大學資訊科技系

20 深度優先搜尋法 DFS 深度優先搜尋法是利用「堆疊(Stack)」 從圖形的某一頂點開始走訪，被拜訪過的頂點就會被標示已拜訪的記號
接著走訪此一頂點的所有相鄰並且未拜訪過的頂點中的任意一個頂點，並標示已拜訪的記號 再以該點為新的起點繼續進行深度優先的搜尋 德明科技大學資訊科技系

21 DFS 實例 DFS 輸出為： 1 , 2 , 4 , 8 , 5 , 6 , 3 , 7 德明科技大學資訊科技系

22 德明科技大學資訊科技系

23 德明科技大學資訊科技系

24 德明科技大學資訊科技系

25 廣度優先搜尋法 BFS 廣度優先搜尋法是以「佇列(Queue)」及「遞迴」技巧來走訪
從圖形的某一頂點開始走訪，被拜訪過的頂點就會被標示已拜訪的記號 接著走訪此一頂點的所有相鄰並且尚未拜訪過的頂點中的任意一個頂點，並標示已拜訪的記號 再以該點為新的起點繼續進行廣度優先的搜尋 德明科技大學資訊科技系

26 BFS 實例 BFS 輸出為： 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 德明科技大學資訊科技系

27 德明科技大學資訊科技系

28 德明科技大學資訊科技系

29 DFS與BFS的應用 找出一個無向圖形的擴張樹(spanning tree)
判斷無向圖形是否為一個相連圖形(connected graph) 找出一個無向圖的相連子圖 德明科技大學資訊科技系