第6章 圖形 - par.cse.nsysu.edu.tw.pptVIP

第6章 圖形 目錄 6.1 問題的圖形表示法 6.2 圖形的資料表示 6.3 圖形的走訪或搜尋 6.4 延展樹和最小成本延展樹 6.5 最短路徑 6.6 遞移封閉 6.7 拓樸序列 6.1 問題的圖形表示法 圖形是包含點、和連接點的邊，所構成的離散結構 有時在邊上可能加上權重值 (weight) 或成本值 (cost) 。 6.1.1尤拉迴路 (Euler Circuit) 6.1.2 漢米爾頓迴圈 (Hamiltonian Cycle) 6.1.3旅行銷售員問題 (Traveling Salesperson Problem) 旅行銷售員為推銷公司的商品，希望自公司出發走訪所有指定的城市，且不重複，並回到公司；而走過路徑的總距離（或總花費）要最短（或最小）。這個問題有城市間實際距離（或旅行花費）的考量。 6.1.4頂點覆蓋(Vertex Cover)問題 將博物館的展示空間用圖形來表示，擺放藝術品的直線走道是邊，頂點是邊與邊交界處。 基於安全的考量，館方將設置最少的警衛希望能監看所有的展示走道。 這就是典型的頂點覆蓋問題：在圖形中，挑最小的頂點集合，使得任何一邊的兩個頂點中，至少有一頂點在所挑的集合中，（所挑的點集合可覆蓋所有的點）。 所挑出的頂點，其分支出的邊，即稱其能覆蓋 (cover) 的邊。 6.2 圖形的專有名詞 我們常用G = (V, E) 來描述一個圖形，其中 V是一個包含所有頂點有限集合 E是連接V中頂點的邊所構成的集合 V = {v1, v2,…, vn} E = {e1, e2,…, em} n 0，m ? 0。 6.2 圖形的專有名詞 無向圖、有向圖 若邊不具方向性，稱為「無向圖」(undirected graph) 6.2 圖形的專有名詞 圖6-9 完備圖 6.2 圖形的專有名詞 子圖 　圖形G = (V, E) 的「子圖」 (subgraph) G‘ = (V’, E‘) ，必須滿足V’ ? V且E‘ ? E。 6.2 圖形的專有名詞 路徑，簡單路徑、長度、迴圈 在圖形中，一條從u到v的「路徑」 (path) ，是由頂點u---…--v及其連接的邊 (u,), (,), …, (, v) （或 u,, ,, …, ,v）所構成；我們以u---…--v表示此u到v的路徑。 一條路徑的「長度」 (length) 即為該路徑包含的所有邊數。 一條「簡單路徑」 (simple path) 指的是除了起點和終點外，其它的頂點皆不同的路徑。 「迴圈」 (cycle) 指的是起點和終點相同的簡單路徑。 6.2 圖形的專有名詞 相連的頂點、或圖形、相連組合 在無向圖形G = (V, E) 中，如果頂點u存在一條路徑連接到頂點v，則稱頂點u和v是「相連的」 (connected) ，（也可說是v和u是相連的）； 而「無向圖形是相連的」表示任兩個頂點u和v皆為相連的。 無向圖形G的「相連組合」 (connected component) C指的是圖中的最大相連的子圖，應即C是G的相連子圖中最大的。 6.2 圖形的專有名詞 強固相連、強固相連組合 在有向圖形G = (V, E) 中，若G的任兩個頂點u和v，都有兩條路徑，一條由u往v，一條由v往u，則稱G為「強固相連的」 (strongly connected) 。 「強固相連組合」 (strongly connected component) 指的是有向圖形中，最大而且強固相連的子圖。 6.2 圖形的專有名詞 6.2 圖形的專有名詞 沒有迴圈 不存在迴圈的圖形稱為「沒有迴圈」 (acyclic) ，一棵樹即為相連、但沒有迴圈的圖形。 圖形是比樹更一般化的資料結構，自然原先對樹所做的動作或運算均可在圖形上探索。 6.2 圖形的資料表示 就像樹一樣，圖形也可用不同的資料結構來表示，下面我們介紹二種常用的資料結構：「相鄰矩陣」和「相鄰串列」。 那種資料結構比較適合，則視圖形的種類、應用的範疇及需要的運算而定。 6.2.1 相鄰矩陣 相鄰矩陣 (adjacent matrix) 即將圖形中頂點是否相鄰的關係紀錄在矩陣中。 若G = (V, E) ，而 |V| = n，即G有n個頂點，則任兩點是否相鄰可用一個存放0和1的n?n二維陣列A表示之： 令i, j ? V 若 (i, j) ? E （或i, j ? E），則令A[i][j]=1 否則令A[i][j]=0。 6.2.2 相鄰串列 若圖形中頂點u的分支度為k，我們可以將與u相鄰的這k個頂點用鍵節串列存放之，那麼如此形成的n個鍵結串列，即構成此圖形的相鄰串列 (adjacent list) 表示。 6.3圖形的走訪或搜尋