1、第 2 2 頁7.1 7.1 圖的術語與定義圖的術語與定義l圖的定義圖的定義圖圖(Graph)圖圖G是由兩個集合是由兩個集合 V(G) 和和E(G) 組成的組成的，記為記為 G=(V,E) 其中：其中：V(G) 是頂點的非空有限集是頂點的非空有限集 E(G) 是邊的有限集合，邊是頂點的是邊的有限集合，邊是頂點的無序對無序對或或有序對有序對。圖的分類圖的分類n 有向圖有向圖n 無向圖無向圖第 3 3 頁7.1 7.1 圖的術語與定義圖的術語與定義l圖的定義圖的定義有向圖有向圖有向圖有向圖G是由兩個集合是由兩個集合 V(G) 和和E(G) 組成的組成的。 其中：其中： V(G) 是頂點的非空有限集

2、是頂點的非空有限集。 E(G) 是是有向邊有向邊（也稱?。┑挠邢藜?，（也稱?。┑挠邢藜?，弧是頂點的有序對，記為弧是頂點的有序對，記為 ，v、w是是頂點頂點，v為為弧尾弧尾，w為為弧頭弧頭。第 4 4 頁7.1 7.1 圖的術語與定義圖的術語與定義l例如：例如： G1 = V1 = A, B, C, D, E E1 = , , , , , , EACBD第 5 5 頁7.1 7.1 圖的術語與定義圖的術語與定義l圖的定義圖的定義無向圖無向圖無向圖無向圖G是由兩個集合是由兩個集合 V(G) 和和E(G) 組成的組成的。其中：其中： V(G) 是頂點的非空有限集是頂點的非空有限集。 E(G) 是

3、邊的有限集合，邊是頂點的無序是邊的有限集合，邊是頂點的無序對，記為對，記為 (v, w) 或或 (w, v)，并且并且 (v, w) = (w, v)。第 6 6 頁7.1 7.1 圖的術語與定義圖的術語與定義l例如：例如： G2 = V2 = v0, v1, v2, v3, v4 E2 = (v0, v1), (v0, v3), (v1, v2), (v1, v4), (v2, v3), (v2, v4) V0V4V3V1V2第 7 7 頁7.1 7.1 圖的術語與定義圖的術語與定義l例如：例如： G2 = V2 = v0，v1，v2，v3 E2 = , , , 例例245136G1圖圖G1

4、中：中：V(G1) = 1 , 2 , 3 , 4 , 5, 6 E(G1) = , , , , , , V0V1V2V3第 8 8 頁7.1 7.1 圖的術語與定義圖的術語與定義l圖的應用舉例圖的應用舉例例例1. 交通圖（公路、鐵路）交通圖（公路、鐵路） 頂點頂點：地點：地點邊邊：連接地點的路：連接地點的路例例2. 電路圖電路圖 頂點頂點：元件：元件邊邊：連接元件之間的線路：連接元件之間的線路例例3. 通訊線路圖通訊線路圖 頂點頂點：地點：地點邊邊：地點間的連線：地點間的連線例例4. 各種流程圖各種流程圖如產品的生產流程圖。如產品的生產流程圖。 頂點頂點：工序：工序邊邊：各道工序之間的順序關

5、系：各道工序之間的順序關系第 9 9 頁7.1 7.1 圖的術語與定義圖的術語與定義圖的基本術語圖的基本術語l鄰接點及關聯邊鄰接點及關聯邊 鄰接點：邊的兩個頂點鄰接點：邊的兩個頂點 關聯邊：若邊關聯邊：若邊 e = (v, u), 則稱頂點則稱頂點v、u 關連關連邊邊 e。e eV0V4V3V1V2第 1010 頁7.1 7.1 圖的術語與定義圖的術語與定義l頂點的度、入度、出度頂點的度、入度、出度 頂點頂點V的度的度 = 與與V相關聯的邊的數目相關聯的邊的數目 在有向圖中：在有向圖中： 頂點頂點V的出度的出度 = 以以V為起點有向邊數為起點有向邊數 頂點頂點V的入度的入度 = 以以V為終點有

6、向邊數為終點有向邊數 頂點頂點V的度的度 = V的出度的出度+V的入度的入度 設圖設圖G 的頂點數為的頂點數為 n，邊數為，邊數為 e 圖的所有頂點的度數和圖的所有頂點的度數和 = 2 2* *e e （每條邊對圖的所有頂點的度數和（每條邊對圖的所有頂點的度數和“貢獻貢獻”2度）度） 第 1111 頁7.1 7.1 圖的術語與定義圖的術語與定義l路徑、回路路徑、回路 無向圖無向圖 G = (V, E) 中的頂點序列中的頂點序列 v1, v2, , vk，若，若 (vi, vi+1) E ( i=1, 2 , k-1 )， v=v1, u=vk，則稱該序列是，則稱該序列是從從 頂點頂點v 到到

7、頂點頂點u 的路的路徑徑；若；若v=u，則稱該序列為，則稱該序列為回路回路。 有向圖有向圖 D = (V, E) 中的頂點序列中的頂點序列 v1, v2, , vk，若，若 E ( i=1,2,k-1 )，v=v1，u=vk，則稱該序列是從，則稱該序列是從 頂點頂點v 到到 頂點頂點u 的路的路徑；若徑；若 v=u，則稱該序列為，則稱該序列為回路回路。第 1212 頁7.1 7.1 圖的術語與定義圖的術語與定義l例如例如 在在圖圖G1中，中，V0, V1, V2, V3 是是 V0 到到 V3 的路徑；的路徑；V0, V1, V2, V3, V0 是回路。是回路。無向圖無向圖G1有向圖有向圖G

8、2V0V4V3V1V2V0V1V2V3 在在圖圖G2中，中，V0, V2, V3 是是 V0 到到 V3 的路的路徑；徑； V0, V2, V3, V0 是回路。是回路。第 1313 頁7.1 7.1 圖的術語與定義圖的術語與定義l連通圖（強連通圖）連通圖（強連通圖） 在無（有）向圖在無（有）向圖 G= 中，若對任何中，若對任何兩個頂點兩個頂點 v、u 都存在從都存在從 v 到到 u 的路徑，則的路徑，則稱稱G是連通圖（強連通圖）。是連通圖（強連通圖）。 非連通圖非連通圖 連通圖連通圖 強連通圖強連通圖 非強連通圖非強連通圖V0V1V2V3V0V2V3V1V5V4V0V1V2V3V0V4V3V

9、1V2第 1414 頁7.1 7.1 圖的術語與定義圖的術語與定義l子圖子圖 設有兩個圖設有兩個圖 G=(V，E)，G1=(V1，E1)，若若 V1 V，E1 E，E1關聯的頂點都在關聯的頂點都在 V1 中，則稱中，則稱 G1 是是 G 的子圖。的子圖。l例例 (b)、(c) 是是 (a) 的子圖的子圖(a)(a)(b)(b)(c)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2第 1515 頁7.1 7.1 圖的術語與定義圖的術語與定義l連通分圖（強連通分量）連通分圖（強連通分量）無向圖無向圖G的極大連通子圖稱為的極大連通子圖稱為G的連通分量。的連通分量。極大連通子圖極大連

10、通子圖含義：該子圖是含義：該子圖是G連通子圖，連通子圖，將將G的任何不在該子圖中的頂點加入，子圖的任何不在該子圖中的頂點加入，子圖不再連通。不再連通。連通分量連通分量非連通圖非連通圖V0V2V3V1V5V4第 1616 頁7.1 7.1 圖的術語與定義圖的術語與定義l連通分圖（強連通分量）連通分圖（強連通分量） 有向圖有向圖D的極大強連通子圖稱為的極大強連通子圖稱為D的強連通的強連通分量。分量。 極大強連通子圖極大強連通子圖含義：該子圖是含義：該子圖是 D 的強連的強連通子圖，將通子圖，將 D 的任何不在該子圖中的頂點加的任何不在該子圖中的頂點加入，子圖不再是強連通的。入，子圖不再是強連通的。

11、強連通分量強連通分量 V0V0 V2V2 V3V3 V1V1V0V1V2V3第 1717 頁7.1 7.1 圖的術語與定義圖的術語與定義l生成樹生成樹 包含無向圖包含無向圖 G 所有頂點的極小連通子圖稱所有頂點的極小連通子圖稱為為G生成樹。生成樹。 極小連通子圖極小連通子圖含義：該子圖是含義：該子圖是G的連通子的連通子圖，在該子圖中刪除任何一條邊，子圖不再圖，在該子圖中刪除任何一條邊，子圖不再連通，若連通，若T是是G的生成樹當且僅當的生成樹當且僅當T滿足如下滿足如下條件：條件： T是是G的連通子圖的連通子圖 T包含包含G的所有頂點的所有頂點 T中無回路中無回路連通圖連通圖G1G1G1G1的生成

12、樹的生成樹V0V4V3V1V2V0V4V3V1V2第 1818 頁7.2 7.2 圖的存儲結構圖的存儲結構一、數組表示法（鄰接矩陣表示）一、數組表示法（鄰接矩陣表示） 鄰接矩陣鄰接矩陣：G的鄰接矩陣是滿足如下條件的鄰接矩陣是滿足如下條件的的 n 階矩陣：階矩陣：Aij=Aij=1 1 若若(v(vi i,v,vj) ) E E 或或 v E E0 0 否則否則0 1 0 1 00 1 0 1 01 10 1 0 10 1 0 10 1 0 1 10 1 0 1 11 10 1 0 00 1 0 00 1 1 0 00 1 1 0 0在數組表示法中，用鄰接在數組表示法中，用鄰接矩陣表示頂點間的關

13、系矩陣表示頂點間的關系0 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 11 10 0 00 0 0V0V1V2V3V0V4V3V1V2第 1919 頁7.2 7.2 圖的存儲結構圖的存儲結構二、鄰接表二、鄰接表鄰接表是圖的鏈式存儲結構鄰接表是圖的鏈式存儲結構1、無向圖的鄰接表、無向圖的鄰接表 頂點：通常按編號順序將頂點數據存儲在一頂點：通常按編號順序將頂點數據存儲在一維數組中；維數組中； 關聯同一頂點的邊：用線性鏈表存儲。關聯同一頂點的邊：用線性鏈表存儲。 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 13 3V

14、0V4V3V1V20 02 24 41 13 34 40 02 21 12 2鄰接點鄰接點的位置的位置第 2020 頁7.2 7.2 圖的存儲結構圖的存儲結構ltypedef struct ArcNode / 結點定義結點定義 int adjvex; / 鄰接點域，鄰接點域，/ 存放與存放與Vi鄰接的點在表頭數組中的位置鄰接的點在表頭數組中的位置 struct ArcNode * *next; / 鏈域，下一條邊或弧鏈域，下一條邊或弧 ArcNode;adjvex nextvexdata firstarcltypedef struct tnode / 表頭結點表頭結點 int vexdata;

15、 / 存放頂點信息存放頂點信息 ArcNode * * firstarc; / 指指向向第一個鄰接點第一個鄰接點 VNode, AdjList MAX_VERTEX_NUM ;ltypedef struct AdjList vertices; int vexnum, arcnum; / 頂點數和弧數頂點數和弧數int kind; / 圖的種類圖的種類第 2121 頁7.2 7.2 圖的存儲結構圖的存儲結構l無向圖采用鄰接表存儲的特點無向圖采用鄰接表存儲的特點 1）在）在G鄰接表中，同一條邊對應兩個結點；鄰接表中，同一條邊對應兩個結點； 2）頂點）頂點v的度：等于的度：等于v對應線性鏈表的長度；

16、對應線性鏈表的長度； 3）判定兩頂點）判定兩頂點v ，u是否鄰接：要看是否鄰接：要看v對應線性對應線性鏈表中有無對應的結點。鏈表中有無對應的結點。 4）在）在G中增減邊：要在兩個單鏈表插入、刪除中增減邊：要在兩個單鏈表插入、刪除結點；結點； 5）設存儲頂點的一維數組大小為）設存儲頂點的一維數組大小為 m（ m 圖的圖的頂點數頂點數 n），圖的邊數為），圖的邊數為 e，G占用存儲空間為：占用存儲空間為：m+2* *e。G占用存儲空間與占用存儲空間與G的頂點數、邊數均有的頂點數、邊數均有關；適用于關；適用于邊稀疏的圖邊稀疏的圖。第 2222 頁7.2 7.2 圖的存儲結構圖的存儲結構二、鄰接表二、

17、鄰接表2、有向圖的鄰接表、有向圖的鄰接表頂點：用一維數組存儲（按編號順序）頂點：用一維數組存儲（按編號順序）以同一頂點為以同一頂點為起點起點的?。河镁€性鏈表存儲的弧：用線性鏈表存儲1234v0v2v3v1vexdata firstarc 3 2 4 1adjvex next類似于無向圖的鄰接表，所不同的是：類似于無向圖的鄰接表，所不同的是：以同一頂點為以同一頂點為起點起點的?。河镁€性鏈表存儲的弧：用線性鏈表存儲V0V1V2V3弧尾弧尾的的位置位置第 2323 頁7.2 7.2 圖的存儲結構圖的存儲結構二、鄰接表二、鄰接表3、有向圖的逆鄰接表、有向圖的逆鄰接表頂點：用一維數組存儲（按編號順序）頂

18、點：用一維數組存儲（按編號順序）以同一頂點為以同一頂點為終點終點的弧：用線性鏈表存儲。的弧：用線性鏈表存儲。1234v0v2v3v1vexdata firstarc 4 1 1 3類似于有向圖的鄰接表，所不同的是：類似于有向圖的鄰接表，所不同的是：以同一頂點為以同一頂點為終點終點弧：用線性鏈表存儲弧：用線性鏈表存儲V0V1V2V3弧頭弧頭的的位置位置第 2424 頁7.2 7.2 圖的存儲結構圖的存儲結構三、有向圖的十字鏈表表示法三、有向圖的十字鏈表表示法弧結點：弧結點：typedef struct ArcBox int tailvex, headvex; / 弧尾、弧頭在表頭數組中位置弧尾、

19、弧頭在表頭數組中位置 struct arcnode *hlink； / 指向弧頭相同的下一條弧指向弧頭相同的下一條弧 struct arcnode * *tlink; / 指向弧尾相同的下一條弧指向弧尾相同的下一條弧 ArcBox;tailvex headvex hlink tlink頂點結點：頂點結點：typedef struct VexNode VertexType data; / 存與頂點有關信息存與頂點有關信息 ArcBox *firstin； / 指向以該頂點為弧頭的第指向以該頂點為弧頭的第1個弧結點個弧結點 ArcBox *firstout; / 指向以該頂點為弧尾的第指向以該頂點

20、為弧尾的第1個弧結點個弧結點 VexNode;VexNode OLGraphM; data firstin firstout第 2525 頁7.2 7.2 圖的存儲結構圖的存儲結構三、有向圖的十字鏈表表示法三、有向圖的十字鏈表表示法例例bdacab cd12341 31 23 43 14 34 24 1相同相同弧尾弧尾相同相同弧頭弧頭第 2626 頁7.2 7.2 圖的存儲結構圖的存儲結構四、四、無向圖的鄰接多重表表示法無向圖的鄰接多重表表示法頂點結點：頂點結點：typedef struct VexBox VertexType data; / 存與頂點有關的信息存與頂點有關的信息 EBox *

21、 * firstedge; / 指向第一條依附于該頂點的指向第一條依附于該頂點的邊邊 VexBox;VexBox AMLGraphM;data firstedge邊結點：邊結點：typedef struct node VisitIf mark; / 標志域標志域，記錄是否已經搜索過，記錄是否已經搜索過 int ivex, jvex; / 該邊依附的兩個頂點在表頭數組中位置該邊依附的兩個頂點在表頭數組中位置 struct EBox * * ilink, * * jlink; /分別指向依附于分別指向依附于ivex和和jvex的下一條邊的下一條邊 EBox;mark ivex ilink jvex

22、 jlink第 2727 頁7.2 7.2 圖的存儲結構圖的存儲結構四、四、無向圖的鄰接多重表表示法無向圖的鄰接多重表表示法例例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2第 2828 頁7.3 7.3 圖的遍歷圖的遍歷l圖的遍歷圖的遍歷訪遍圖中所有的頂點，并且使圖中的每訪遍圖中所有的頂點，并且使圖中的每個頂點僅被訪問一次。個頂點僅被訪問一次。l遍歷實質遍歷實質找每個頂點的鄰接點。找每個頂點的鄰接點。l搜索路徑搜索路徑深度優先遍歷（深度優先遍歷（DFS）廣度優先遍歷（廣度優先遍歷（BFS）第 2929 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷（圖的深度

23、遍歷（DFS）從圖的某頂點從圖的某頂點v出發，進行深度優先遍歷出發，進行深度優先遍歷 訪問頂點訪問頂點 v ； for ( v 的所有鄰接點的所有鄰接點 w1、w2、w3 ) 若若 wi 未被訪問，則從未被訪問，則從 wi 出發，進行出發，進行深度優先遍歷。深度優先遍歷。vw1SG1SG2SG3w2w3w2第 3030 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷（圖的深度遍歷（DFS） 從圖的某一頂點從圖的某一頂點 V0 出發，訪問此頂點；出發，訪問此頂點；然后依次從然后依次從 V0 的的未被訪問未被訪問的鄰接點出發，的鄰接點出發，深深度優先遍歷度優先遍歷圖，直至圖中所有和圖，直至圖中所

24、有和 V0 相通的頂相通的頂點都被訪問到；點都被訪問到； 若此時圖中尚有頂點未被訪問，則另選若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止過程，直至圖中所有頂點都被訪問為止。第 3131 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷（圖的深度遍歷（DFS）例：例：achdekfach dkfe achkfed訪問次序訪問次序bg第 3232 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷（圖的深度遍歷（DFS）例：例：bgachdekfach dkfe achkfedbg訪問次序訪問次序b

25、g第 3333 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷（圖的深度遍歷（DFS）V1V2V4V5V3V7V6V8例：例：深度遍歷：深度遍歷： V1V2V4V8V5V3V6V7第 3434 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷（圖的深度遍歷（DFS）V1V2V4V5V3V7V6V8例例1深度遍歷深度遍歷1：V1V2 V4 V8 V5 V6 V3 V7 由于由于沒有規定訪問鄰接點的順序沒有規定訪問鄰接點的順序，所以深度優，所以深度優先序列不唯一。先序列不唯一。深度遍歷深度遍歷2：V1V3 V7 V8 V6 V5 V2 V4第 3535 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深

26、度遍歷（圖的深度遍歷（DFS）V1V2V4V5V3V7V6V8例例深度遍歷：深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5第 3636 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷（圖的深度遍歷（DFS）算法算法7.4和和7.5開始開始初始化初始化標志數組標志數組v=0V訪問過訪問過?DFS(g, v)v=v+1v VexNum結束結束NYYNDFS開始開始訪問訪問v，置置標志標志求求v的的鄰接點鄰接點有鄰接點有鄰接點w求下一鄰接點求下一鄰接點W訪問過訪問過結束結束NYNYDFS(G, w)第 3737 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷（圖的深度遍歷（DFS）遞歸

27、算法遞歸算法void DFSTrav( Graph G, Void ( * Visit ) ( VertexType e ) ) for ( v=0; v G.vexnum; +v ) / 初始化標志數組初始化標志數組 visitedv = FALSE; for ( v=0; v= 0; w = NextAdjVex(G, v, w) ) if ( ! visited w ) DFS( G, w, Visit( w ) ); /DFS訪問標志數組：訪問標志數組：int visited 全局變量，初始時所有分量全為全局變量，初始時所有分量全為 FALSE第 3939 頁7.3 7.3 圖的遍歷圖

28、的遍歷l圖的深度遍歷（圖的深度遍歷（DFS）遞歸算法遞歸算法V1V2V4V5V3V7V6V8例例深度遍歷：深度遍歷：V112341342vexdata firstarc 2 7 8 3adjvex next55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V4第 4040 頁7.3 7.3 圖的遍歷圖的遍歷l圖的深度遍歷（圖的深度遍歷（DFS）遞歸算法遞歸算法V1V2V4V5V3V7V6V8例例12341342vexdata firstarc 2 7 8 3adjvex next55 6 4 8 2678678 7深度遍歷：深度遍歷：V

29、1V3 V7 V6 V2 V4 V8 V5第 4141 頁7.3 7.3 圖的遍歷圖的遍歷l深度優先遍歷的時間復雜度深度優先遍歷的時間復雜度DFS對每一條邊處理一次（無向圖的每條邊從對每一條邊處理一次（無向圖的每條邊從兩個方向處理），每個頂點訪問一次。兩個方向處理），每個頂點訪問一次。鄰接表表示總代價為：鄰接表表示總代價為：O( 點數點數n + 邊數邊數e )鄰接矩陣表示鄰接矩陣表示n處理所有的邊需要處理所有的邊需要 O(nO(n2 2) ) 的時間，所以的時間，所以總代價為總代價為 O(n+nO(n+n2 2)= O(n)= O(n2 2) )。第 4242 頁7.3 7.3 圖的遍歷圖的遍

30、歷l圖的廣度遍歷（圖的廣度遍歷（BFS）從圖中某頂點從圖中某頂點v v出發：出發： 1) 1)訪問頂點訪問頂點v v； 2) 2)訪問訪問 v v 所有未被訪問的鄰接點所有未被訪問的鄰接點 w1, w2, w1, w2, wkwk； 3) 3)依次從這些鄰接點出發，訪問其所有未依次從這些鄰接點出發，訪問其所有未被訪問的鄰接點。依此類推，直至圖中所有被訪問的鄰接點。依此類推，直至圖中所有和和 v0 v0 有路徑相通的頂點都被訪問到。有路徑相通的頂點都被訪問到。第 4343 頁7.3 7.3 圖的遍歷圖的遍歷l圖的廣度遍歷（圖的廣度遍歷（BFS） 從圖中某一頂點從圖中某一頂點 V0 V0 出發，訪

31、問此頂點后出發，訪問此頂點后，依次訪問，依次訪問 V0 V0 的各個未曾訪問過的鄰接點；的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發，然后分別從這些鄰接點出發，廣度優先遍歷廣度優先遍歷圖圖，直至圖中所有已被訪問的頂點的鄰接點都被，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；訪問到； 若此時圖中尚有頂點未被訪問，則另選圖若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點，直至圖中所有頂點均均被訪問為止被訪問為止。第 4444 頁7.3 7.3 圖的遍歷圖的遍歷l圖的廣度遍歷（圖的廣度遍歷（BFS）V1V2

32、V4V5V3V7V6V8例：例：廣度遍歷：廣度遍歷：V1 V2 V3V4V5 V6 V7V8第 4545 頁7.3 7.3 圖的遍歷圖的遍歷l圖的廣度遍歷（圖的廣度遍歷（BFS）例：例：abchdekfgacdef h k achkfed訪問次序訪問次序第 4646 頁7.3 7.3 圖的遍歷圖的遍歷l圖的廣度遍歷（圖的廣度遍歷（BFS）遞歸算法遞歸算法開始開始初始化標志數組初始化標志數組v=0v訪問過訪問過BFSv=v+1v Vexnum結束結束NYYN第 4747 頁7.3 7.3 圖的遍歷圖的遍歷l圖的廣度遍歷（圖的廣度遍歷（BFS）遞歸算法遞歸算法void BFSTraverse( G

33、raph G, void (* Visit) ( VertexType ) ) /本算法對圖本算法對圖G進行廣度優先遍歷進行廣度優先遍歷 for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 訪問標志數組初始化訪問標志數組初始化 for ( v=0; vG.vexnum; +v ) if ( ! visitedv ) BFS( G, v, Visit ); /BFSTraverse第 4848 頁7.3 7.3 圖的遍歷圖的遍歷l圖的廣度遍歷（圖的廣度遍歷（BFS）算法算法7.6開始開始訪問訪問v0，置置標志標志求求V鄰接點鄰接點 ww存在嗎存在嗎V下一

34、鄰接點下一鄰接點ww訪問過訪問過結束結束NYNYBFS初始化隊列初始化隊列v0入隊入隊隊列空嗎隊列空嗎隊頭隊頭 v 出隊出隊訪問訪問w，置置標志標志w入隊入隊NY第 4949 頁7.3 7.3 圖的遍歷圖的遍歷void BFS( Graph G, int v, void(* Visit) (VertexType e) ) / 從第從第v個頂點出發個頂點出發 InitQueue(Q); / 建立輔助空隊列建立輔助空隊列Q Visit(v); visitedv=TRUE; / 訪問訪問u，訪問標志數組，訪問標志數組 EnQueue( Q, v ); / v入隊入隊 while ( ! QueueE

35、mpty( Q ) ) / 隊列非空則執行循環隊列非空則執行循環 DeQueue( Q, u ); / 隊頭元素出隊，并賦值給隊頭元素出隊，并賦值給u for ( w=FirstAdjVex(G,u); w; w=NextAdjVex(G,u,w) ) if ( ! visitedw ) / 若該結點尚未被訪問過若該結點尚未被訪問過 Visit(w); / 訪問訪問w visitedw=TRUE; / 標記標記w已被訪問已被訪問 EnQueue(Q,w); / w入隊入隊 /while /BFS第 5050 頁7.3 7.3 圖的遍歷圖的遍歷l圖的廣度遍歷（圖的廣度遍歷（BFS）例例14235

36、12341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍歷序列：遍歷序列：10 1 2 3 4 54fr遍歷序列：遍歷序列：1 40 1 2 3 4 54 3fr遍歷序列：遍歷序列：1 4 3第 5151 頁7.3 7.3 圖的遍歷圖的遍歷l圖的廣度遍歷（圖的廣度遍歷（BFS）例例142350 1 2 3 4 54 3 2fr遍歷序列：遍歷序列：1 4 3 20 1 2 3 4 5 3 2fr遍歷序列：遍歷序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍歷序列：遍歷序列：1 4 3 2

37、512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 2第 5252 頁7.3 7.3 圖的遍歷圖的遍歷l圖的廣度遍歷（圖的廣度遍歷（BFS）例例142350 1 2 3 4 5 2 5fr遍歷序列：遍歷序列：1 4 3 2 50 1 2 3 4 5 5fr遍歷序列：遍歷序列：1 4 3 2 50 1 2 3 4 5 fr遍歷序列：遍歷序列：1 4 3 2 512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 2第 5353 頁7.3 7.3 圖的遍歷圖的遍歷

38、l遍歷的應用遍歷的應用求兩個頂點之間的最短路徑長度求兩個頂點之間的最短路徑長度 廣度優先搜索訪問頂點的次序是按廣度優先搜索訪問頂點的次序是按“路路徑長度徑長度”漸增的次序。漸增的次序。 求路徑長度最短的路徑可以基于廣度優先求路徑長度最短的路徑可以基于廣度優先搜索遍歷進行。搜索遍歷進行。第 5454 頁7.4 7.4 圖的最小生成樹圖的最小生成樹l問題提出問題提出要在要在n個城市間建立通信聯絡網個城市間建立通信聯絡網，如何省錢？，如何省錢？l問題抽象問題抽象 頂點頂點：表示城市表示城市 權權：城市間建立通信線路所需花費代價城市間建立通信線路所需花費代價 希望找到一棵生成樹，它的每條邊上的權希望找

39、到一棵生成樹，它的每條邊上的權值之和（即建立該通信網所需花費的總代價）值之和（即建立該通信網所需花費的總代價）最小最小最小代價生成樹最小代價生成樹 MST（Minimum cost Spanning Tree）網絡中的網絡中的SpaningTree Protocol第 5555 頁7.4 7.4 圖的最小生成樹圖的最小生成樹l利用利用 MST 性質構造最小生成樹性質構造最小生成樹 若若 U 集是集是 V 的一個非空子集，若的一個非空子集，若 (u0, v0)是一條是一條最小權值的邊最小權值的邊，其中，其中 u0 U，v0 V-U；則：則：(u0, v0) 必在最小生成樹上必在最小生成樹上。 U

40、V-U v0u0 V第 5656 頁7.4 7.4 圖的最小生成樹圖的最小生成樹lMST性質證明：用反證法性質證明：用反證法假設連通網假設連通網 N 的任何一棵最小生成樹都不包含邊的任何一棵最小生成樹都不包含邊 (u0,v0)。設。設 T 是連通網上的一棵最小生成樹，當把是連通網上的一棵最小生成樹，當把邊邊 (u0, v0) 加入到加入到 T 中時，由生成樹的定義知，中時，由生成樹的定義知，T中必存在一條包含中必存在一條包含 (u0, v0) 的回路。的回路。而另一方面，由于而另一方面，由于 T 是生成樹，則在是生成樹，則在 T 上必存在另上必存在另一條邊一條邊 (u ,v )，其中，其中 u

41、 U，v V-U，且，且 u0 和和u 之間，之間，v0 和和 v 之間均有路徑相通。刪去邊之間均有路徑相通。刪去邊(u ,v )，便可消除上述回路，同時得到另一棵包含，便可消除上述回路，同時得到另一棵包含邊邊 (u0, v0) 生成樹生成樹 T 。因為因為 (u0, v0) 的代價不大于的代價不大于 (u ,v ) 的代價，所以的代價，所以 T 的代價也不大于的代價也不大于 T 的代價。與假設矛盾，因此命的代價。與假設矛盾，因此命題成立。題成立。第 5757 頁7.4 7.4 圖的最小生成樹圖的最小生成樹l利用利用 MST 性質構造最小生成樹性質構造最小生成樹 若若 U 集是集是 V 的一個

42、非空子集，若的一個非空子集，若 (u0, v0)是一條是一條最小權值的邊最小權值的邊，其中，其中 u0 U，v0 V-U；則：則：(u0, v0) 必在最小生成樹上必在最小生成樹上。 l典型算法典型算法普里姆普里姆(Prim)算法算法將頂點歸并將頂點歸并，與邊數無關，適于，與邊數無關，適于稠密網稠密網。克魯斯卡爾克魯斯卡爾(Kruskal)算法算法將邊歸并將邊歸并，適于求，適于求稀疏網稀疏網的最小生成樹。的最小生成樹。第 5858 頁7.4 7.4 圖的最小生成樹圖的最小生成樹 普里姆算法（普里姆算法（Prim）設設 G=(V, GE) 為一個具有為一個具有 n 個頂點的連通個頂點的連通網絡，

43、網絡，T=(U, TE) 為構造的生成樹。為構造的生成樹。(1) 初始時，初始時，U = u0，TE = ；(2) 在所有在所有 u U 且且 v V- -U 的邊的邊 (u, v) 中選中選擇一條權值最小的邊，不妨設為擇一條權值最小的邊，不妨設為 (u,v)；(3) (u,v) 加入加入TE，同時將，同時將 v 加入加入U；(4) 重復重復(2)(3)，直到，直到 U=V 為止；為止；UV-U vu U擴大擴大V-U縮小縮小vu 第 5959 頁7.4 7.4 圖的最小生成樹圖的最小生成樹 普魯姆算法（普魯姆算法（Prim）教材教材P175V V3 3V V1 1V V4 4V V6 6V

44、V5 5V V2 23 36 65 52 21 16 65 55 54 46 6V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 12 2V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 14 4V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 14 42 2V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 14 45 52 2V V3 3V V1 1V V4 4V V6 6V V5 5V V2 21 14 45 53 3U= U= V1V1 U= U= V1,V3V1,V3 U= U= V

45、1,V3,V6V1,V3,V6U= U= V1,V3,V6,V4V1,V3,V6,V4 U= U= V1,V3,V6,V4,V2V1,V3,V6,V4,V2 U= U= V1,V3,V6,V4,V2,V5V1,V3,V6,V4,V2,V5 第 6060 頁7.4 7.4 圖的最小生成樹圖的最小生成樹l輔助數組輔助數組closedge struct VertexType Adjvex; / 相關頂點相關頂點 VRType lowcost; / 最小邊的權值最小邊的權值 closedge MAX_VERTEX_NUM ; Closedge. Adjvex v ： 頂點頂點v到子集到子集U中中權最小

46、邊權最小邊 (v, u) 關聯的關聯的頂點頂點u Closedge.lowcostv： 頂點頂點v到子集到子集U權權最小邊最小邊 (v, u) 的權值的權值( (距離距離) )closedge.Adjvexclosedge.Lowcost 1 2 3 4 5 61 2 3 4 5 6第 6161 頁7.4 7.4 圖的最小生成樹圖的最小生成樹 V1V1 V1 V1 V1V1 V1 V1 V1 V1 V1 V1 0 0 6 6 1 1 5 5 max maxmax max 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) closedge.Adjvex closedge.L

47、owcost 3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1 V1 V1 V3 V3 V1V1 V1 V3 V3 V1 V3 V3 0 0 5 5 1 1 5 5 6 46 4 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) closedge.Adjvex closedge.Lowcost3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1第 6262 頁7.4 7.4 圖的最小生成樹圖的最小生成樹 V3 V3 V1 V1 V1 V3 V1 V3 V3V

48、3 0 0 5 5 1 1 5 6 5 6 4 4 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) closedge.Adjvex closedge.Lowcost 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) V3 V3 V1V1 V6 V3 V6 V3 V3V3 0 0 5 5 1 1 2 6 2 6 4 4closedge.Adjvex closedge.Lowcost 3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V13 36 65 52 21 16 65 55 54 46 6V

49、6V6V5V5V4V4V3V3V2V2V1V1第 6363 頁7.4 7.4 圖的最小生成樹圖的最小生成樹 V3 V3 V1V1 V6V6 V3 V3 V3V3 0 0 5 5 1 1 2 2 6 6 4 4 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) closedge.Adjvex closedge.Lowcost3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1 V3V3 V1 V1 V6V6 V3 V3 V3V3 0 0 5 5 1 1 2 2 6 6 4 4 0(V1) 1(V2) 2(V3) 3(V

50、4) 4(V5) 5(V6)closedge.Adjvex closedge.Lowcost3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1第 6464 頁7.4 7.4 圖的最小生成樹圖的最小生成樹 V3 V1 V6V3 V1 V6 V3V3 V3V3 0 5 1 2 0 5 1 2 3 3 4 4 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6) closedge.Adjvex closedge.Lowcost3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2

51、V1V13 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1 V3V3 V1 V1 V6V6 V3 V3 V3V3 0 0 5 5 1 1 2 2 6 6 4 4 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6)closedge.Adjvex closedge.Lowcost第 6565 頁7.4 7.4 圖的最小生成樹圖的最小生成樹 V3 V1 V6 V3 V3V3 V1 V6 V3 V3 0 5 1 2 3 4 0 5 1 2 3 4 0(V1) 1(V2) 2(V3) 3(V4) 4(V5) 5(V6)clos

52、edge.Adjvex closedge.Lowcost3 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V13 36 65 52 21 16 65 55 54 46 6V6V6V5V5V4V4V3V3V2V2V1V1第 6666 頁7.4 7.4 圖的最小生成樹圖的最小生成樹void MiniSpanTree_P( MGraph G, VertexType u ) /用普里姆算法從頂點用普里姆算法從頂點u出發構造網出發構造網G的最小生成樹的最小生成樹 k = LocateVex ( G, u ); for ( j=0; jG.vexnum

53、; +j ) / 輔助數組初始化輔助數組初始化 if (j!=k) closedgej = u, G.arcskj ; closedgek.Lowcost = 0; / 初始，初始，Uu for ( i=0; iG.vexnum; +i ) 繼續向生成樹上添加頂點繼續向生成樹上添加頂點;第 6767 頁7.4 7.4 圖的最小生成樹圖的最小生成樹 k = minimum( closedge ); / 求出加入生成樹的下一個頂點求出加入生成樹的下一個頂點(k) printf(closedgek.Adjvex, G.vexsk); / 輸出生成樹上一條邊輸出生成樹上一條邊 closedgek.Lo

54、wcost = 0; / 第第k頂點并入頂點并入U集集 for (j=0; jG.vexnum; +j) /修改其它頂點的最小邊修改其它頂點的最小邊 if ( G.arcskj closedgej.Lowcost ) closedgej = G.vexsk, G.arcskj ; 第 6868 頁7.4 7.4 圖的最小生成樹圖的最小生成樹l普里姆算法的性能普里姆算法的性能 設設 n 是圖的頂點數，普魯姆算法的是圖的頂點數，普魯姆算法的時間復雜度為時間復雜度為 O(n2)。 與邊數無關，與邊數無關，適用于求適用于求邊稠密邊稠密的網的的網的最小生成樹。最小生成樹。第 6969 頁7.4 7.4

55、圖的最小生成樹圖的最小生成樹l克魯斯卡爾克魯斯卡爾(Kruskal)算法算法設連通網設連通網 N = ( V, E )。令最小生成樹令最小生成樹初始狀態為只有初始狀態為只有 n 個頂點而個頂點而無邊的非連通圖無邊的非連通圖 T = (V, )，每個頂點自成，每個頂點自成一個連通分量。一個連通分量。在在E中選取代價最小的邊，若該邊依附的頂中選取代價最小的邊，若該邊依附的頂點落在點落在 T 中中不同的連通不同的連通分量上，則將此邊加入分量上，則將此邊加入到到 T 中；否則，舍去此邊，選取下一條代價最中；否則，舍去此邊，選取下一條代價最小的邊小的邊。依此類推，直至依此類推，直至 T 中所有頂點都在中

56、所有頂點都在同一連同一連通分量通分量上為止上為止。第 7070 頁7.4 7.4 圖的最小生成樹圖的最小生成樹l克魯斯卡爾克魯斯卡爾(Kruskal)算法算法設連通網設連通網 N = ( V, E )。 初始時最小生成樹只包含圖的初始時最小生成樹只包含圖的 n n 個頂個頂點，每個頂點為一棵子樹；點，每個頂點為一棵子樹； 選取權值較小且所關聯的兩個頂點不選取權值較小且所關聯的兩個頂點不在同一子樹的邊，將此邊加入到最小生成樹在同一子樹的邊，將此邊加入到最小生成樹中；中； 重復重復 n-1 n-1 次，即得到包含次，即得到包含 n n 個頂個頂點和點和 n-1 n-1 條邊的最小生成樹。條邊的最小

57、生成樹。第 7171 頁7.4 7.4 圖的最小生成樹圖的最小生成樹l克魯斯卡爾克魯斯卡爾(Kruskal)算法算法構造非連通圖構造非連通圖 ST=( V, );k = i = 0; / k 計選中的邊數計選中的邊數while ( k n-1 ) + i; 檢查邊集檢查邊集 E 中第中第 i 條權值最小的邊條權值最小的邊(u,v); 若若(u,v)加入加入ST后不使后不使ST中產生回路，中產生回路， 則則 輸出邊輸出邊(u,v); 且且 k+;第 7272 頁7.4 7.4 圖的最小生成樹圖的最小生成樹l克魯斯卡爾克魯斯卡爾(Kruskal)算法算法5 56 66 61 15 54 4V3V3

58、V1V1V4V4V6V6V5V5V2V23 36 65 52 216543212345第 7373 頁7.4 7.4 圖的最小生成樹圖的最小生成樹l克魯斯卡爾克魯斯卡爾(Kruskal)算法算法16543212345datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222采用邊集數組保存圖：采用邊集數組保存圖：5 56 66 61 15 54 4V3V3V1V1V4V4V6V6V5V5V2V23 36 65 52 2第 7474 頁7

59、.4 7.4 圖的最小生成樹圖的最小生成樹l克魯斯卡爾的性能克魯斯卡爾的性能 設圖的邊數是設圖的邊數是 e，克魯斯卡爾算法的，克魯斯卡爾算法的時間復雜度為時間復雜度為 O(elog e)。 適用于求邊稀疏的網的適用于求邊稀疏的網的最小生成樹。最小生成樹。第 7575 頁7.4 7.4 圖的最小生成樹圖的最小生成樹l兩種兩種算法算法比較比較普里姆算法普里姆算法克魯斯卡爾算法克魯斯卡爾算法時間復雜度時間復雜度O(n2)O(eloge)稠密圖稠密圖稀疏圖稀疏圖算法名算法名適應范圍適應范圍第 7676 頁7.5 7.5 有向無環圖有向無環圖拓撲排序拓撲排序l問題提出問題提出 不同課程之間的學習次序存在

60、先后次不同課程之間的學習次序存在先后次序，序，學生應按怎樣的順序學習這些課程，學生應按怎樣的順序學習這些課程，才能無矛盾、順利完成學業才能無矛盾、順利完成學業？l問題抽象問題抽象頂點頂點表示課程表示課程有向弧有向弧表示先決條件，若表示先決條件，若 課程課程i 是是 課程課程j 的先決條件，則圖中有弧的先決條件，則圖中有弧。有向無環圖有向無環圖拓撲排序拓撲排序。第 7777 頁7.5 7.5 有向無環圖有向無環圖拓撲排序拓撲排序l有向無環圖有向無環圖(DAG)沒有回路的有向圖。沒有回路的有向圖。含有公共子式的表達式含有公共子式的表達式 ( a + b ) * ( e / f ) - ( a +