綜合數(shù)據(jù)結構07

1、2022-3-11圖的基本概念、圖的存儲結構和圖的常用算法圖的基本概念、圖的存儲結構和圖的常用算法圖的各種存儲方式及其運算圖的各種存儲方式及其運算 圖結構存儲方式的選擇，幾種經(jīng)典圖算法的實現(xiàn)圖結構存儲方式的選擇，幾種經(jīng)典圖算法的實現(xiàn) 圖的基本概念圖的基本概念 圖的存儲結構圖的存儲結構 圖的遍歷圖的遍歷 最小生成樹最小生成樹 最短路徑最短路徑 拓撲排序拓撲排序2022-3-12本章主要介紹圖的基本概念、圖的存儲結構和有關圖本章主要介紹圖的基本概念、圖的存儲結構和有關圖的一些常用算法。通過本章學習，讀者應該：的一些常用算法。通過本章學習，讀者應該：1)了解圖的定義和術語了解圖的定義和術語2)掌握圖

2、的各種存儲結構掌握圖的各種存儲結構3)掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷算法掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷算法 4) 理解最小生成樹、最短路徑、拓撲排序等圖的常用理解最小生成樹、最短路徑、拓撲排序等圖的常用算法算法 2022-3-13圖（圖（GraphGraph）是一種較線性表和樹更為復雜的是一種較線性表和樹更為復雜的非線性結構非線性結構。是對結點的前趨和后繼個數(shù)不加限制的數(shù)據(jù)結構，用來是對結點的前趨和后繼個數(shù)不加限制的數(shù)據(jù)結構，用來描述元素描述元素之間之間“多對多多對多”的關系。的關系。 在線性結構中，結點之間的關系是在線性結構中，結點之間的關系是線性線性關系關系 在樹形結構中，

3、結點之間的關系實質(zhì)上是在樹形結構中，結點之間的關系實質(zhì)上是層次層次關系關系 在圖結構中，對結點（圖中常稱為頂點）的前趨和后繼個數(shù)在圖結構中，對結點（圖中常稱為頂點）的前趨和后繼個數(shù)不加限制的，即結點之間的關系是任意的。不加限制的，即結點之間的關系是任意的。 2022-3-14 2022-3-152022-3-16（a) G1（b) G2（c) G3（d) G452341123467522223645212022-3-17 在圖在圖7-17-1中，圖中，圖( (a)a)為無向圖，其中為無向圖，其中G1G1的頂點集合和邊集合分的頂點集合和邊集合分別為：別為：V(G1)=1V(G1)=1，2 2，3

4、 3，4 4，5 5，6 6，77，E(G1)=(1E(G1)=(1，2)2)，(l(l，3)3)，(2(2，3)3)，(3(3，4)4)，(3(3，5)5)，(5(5，6)6)，(5(5，7)7)。 圖圖( (c)c)為有向圖，其中為有向圖，其中G3G3的頂點集合和弧集合分別為的頂點集合和弧集合分別為V(G3)=1V(G3)=1，2 2，3 3，4 4，5 5，66，E(G3)=，2022-3-187.1.2 圖的基本術語圖的基本術語1 1 頂點的度頂點的度 與頂點與頂點v v相關的相關的邊邊或弧的數(shù)目或弧的數(shù)目稱作頂點稱作頂點v v的度。的度。在有向圖中，在有向圖中，一個頂點依附的弧頭數(shù)目

5、，稱為該頂點的入度。一個頂點依附一個頂點依附的弧頭數(shù)目，稱為該頂點的入度。一個頂點依附的弧尾數(shù)目，稱為該頂點的出度，某個頂點的入度和出度之和的弧尾數(shù)目，稱為該頂點的出度，某個頂點的入度和出度之和稱為該頂點的度。稱為該頂點的度。 例如圖例如圖7-17-1中，無向圖中，無向圖G1G1中頂點中頂點3 3的度為的度為4 4，頂點，頂點5 5的度為的度為3 3。 例如在圖例如在圖7-17-1中，有向圖中，有向圖G3G3中頂點中頂點1 1的出度的出度OD (1)=3OD (1)=3，入度入度ID ID (1)=1(1)=1，其度其度TD (1)=4TD (1)=4。 2022-3-19在無向圖在無向圖G中

6、，若存在一個頂點序列中，若存在一個頂點序列Vp,Vi1，Vi2，Vin，Vq,使得（使得（Vp,Vi1）,(Vi1,Vi2),.，(Vin,Vq)均屬于均屬于E（G），），則稱頂點則稱頂點Vp到到Vq存在一條路徑。存在一條路徑。若一條路徑上除起點和終點可以相同外，其余頂點均不若一條路徑上除起點和終點可以相同外，其余頂點均不相同，則稱此路徑為相同，則稱此路徑為簡單路徑簡單路徑。起點和終點相同的路徑稱為起點和終點相同的路徑稱為回路回路；簡單路徑組成的回路稱為簡單回路。簡單路徑組成的回路稱為簡單回路。路徑上經(jīng)過的路徑上經(jīng)過的邊的數(shù)目邊的數(shù)目稱為該路徑的稱為該路徑的路徑長度路徑長度。2022-3-11

7、02022-3-111邊邊: : 無向圖中無向圖中頂點的偶對，寫成（頂點的偶對，寫成（VxVx，VyVy）或（或（VyVy，VxVx）。）?；』? : 有向圖中頂點的偶對有向圖中頂點的偶對, ,Vx,VyVx,Vy表示從表示從VxVx到到VyVy?；☆^弧頭: : 弧的終點弧的終點弧尾弧尾: : 弧的起點弧的起點弧弧 VxVx，VyVy 弧尾弧尾Vx 弧頭弧頭Vy2022-3-112設有兩個圖設有兩個圖G(V,E)和和G(V,E)。若若V V 且且E E,則稱則稱圖圖G是是圖圖G的子圖。的子圖。2022-3-113（a)（b)52341364521圖圖7-3 7-3 連通分量和強連通分量連通分量

8、和強連通分量 v vi i和和v vj j（v vi i，v vj jVV） 圖圖7-17-1中中G1G1是連通圖，是連通圖，G2G2是非連通圖。是非連通圖。 G2 G2中有中有3 3個連通分量，如圖個連通分量，如圖7-37-3（a a）所示。所示。 2022-3-114 (a) 無向網(wǎng) (b)有向網(wǎng) 圖 7-4 無向帶權圖和有向帶權圖 5 3 1 2 4 4 1 6 7 2 3 5 8 A B C 2 1 5 3 4 或弧或弧權權可以代表一個頂點到另一個頂點的距離，耗費等。可以代表一個頂點到另一個頂點的距離，耗費等。一般稱為一般稱為如圖如圖7-47-4所示所示 2022-3-115非連通圖非

9、連通圖的生成樹則組成一個的生成樹則組成一個生成森林生成森林。若圖中有。若圖中有n n個個頂點，頂點，m m個連通分量，則生成森林中有個連通分量，則生成森林中有n-mn-m條邊。條邊。2022-3-116鄰接點鄰接點頂點頂點: : 圖中的結點圖中的結點 鄰接點鄰接點: :無向圖中無向圖中，若邊，若邊( (x,x,y)y) E E，有向圖中有向圖中，若弧，若弧( (x,x,y)y) E E，VxVyx、y互為鄰接點互為鄰接點VxVyy是是x的鄰接點的鄰接點2022-3-117 圖的基本運算也包括查找、插入和刪除。圖的基本運算也包括查找、插入和刪除。（1 1）頂點定位運算頂點定位運算 確定頂點確定頂

10、點v v在圖中的位置；在圖中的位置；（2 2）取頂點運算取頂點運算 求取圖中第求取圖中第i i個頂點；個頂點；（3 3）求第一個鄰接點運算求第一個鄰接點運算 求圖中頂點求圖中頂點v v的第一個鄰接點；的第一個鄰接點；（4 4）求下一個鄰接點運算求下一個鄰接點運算 已知已知w w為圖中頂點為圖中頂點v v的某個鄰接點，求的某個鄰接點，求頂點頂點w w的下一個鄰接點；的下一個鄰接點；（5 5）插入頂點運算插入頂點運算 在圖中增添一個頂點在圖中增添一個頂點v v作為圖的第作為圖的第n+1n+1個頂點，個頂點，其中其中n n為插入該頂點前圖的頂點個數(shù)；為插入該頂點前圖的頂點個數(shù)；（6 6）插入弧運算插

11、入弧運算 在圖中增添一條從頂點在圖中增添一條從頂點v v到頂點到頂點w w的弧。的弧。（7 7）刪除頂點運算刪除頂點運算 從圖中刪除頂點從圖中刪除頂點v v以及所有與頂點以及所有與頂點v v相關聯(lián)的相關聯(lián)的弧?；?。（8 8）刪除弧運算刪除弧運算 從圖中刪除一條從頂點從圖中刪除一條從頂點v v到頂點到頂點w w的弧。的弧。2022-3-118鄰接矩陣鄰接矩陣(AdjacencyMatrix)是表示頂點之間相鄰關系的矩陣。是表示頂點之間相鄰關系的矩陣。設設G(V，E)是具有是具有n個頂點的圖，則個頂點的圖，則G的鄰接矩陣是具有如下性的鄰接矩陣是具有如下性質(zhì)的質(zhì)的n階方陣。階方陣。Aij=1 對無向

12、圖若存在邊(vi,vj),對有向圖若存在弧0 反之無向圖無向圖的鄰接矩陣是以主對角線的鄰接矩陣是以主對角線對稱對稱的，的，有向圖有向圖的鄰接矩陣可的鄰接矩陣可能是能是不對稱不對稱的。的。在有向圖中：在有向圖中：第第i行行1的個數(shù)就是頂點的個數(shù)就是頂點i的出度，的出度，第第j 列列1的個數(shù)就是頂點的個數(shù)就是頂點j的入度。的入度。在無向圖中在無向圖中,第第i行行(列列)1的個數(shù)就是頂點的個數(shù)就是頂點i的度。的度。2022-3-11914320011000010100101(a)(b)圖圖7-6 有向圖及其鄰接矩陣有向圖及其鄰接矩陣154320010101011001001110010011(a)(

13、b)圖圖7-5無向圖及其鄰接矩陣無向圖及其鄰接矩陣2022-3-120 對于無向圖，（對于無向圖，（vi，vj）和（和（vj，vi）表示同一條邊，因此，表示同一條邊，因此，在鄰接矩陣中在鄰接矩陣中Aij=Aji。 無向圖的鄰接矩陣是（關于主對角線）對稱矩陣，可用主對角無向圖的鄰接矩陣是（關于主對角線）對稱矩陣，可用主對角線以上（或以下）的部分表示。線以上（或以下）的部分表示。 對有向圖，弧對有向圖，弧和和表示方向不同的兩條弧，表示方向不同的兩條弧，Aij和和Aji表示不同的弧，所以有向圖的鄰接矩陣一般不具有對稱性。表示不同的弧，所以有向圖的鄰接矩陣一般不具有對稱性。 鄰接矩陣表示法適合于以頂點

14、為主的運算。鄰接矩陣表示法適合于以頂點為主的運算。2022-3-121對于有向圖，頂點對于有向圖，頂點vi的出度的出度OD(vi)等于鄰接矩陣第等于鄰接矩陣第i行元素行元素之和；頂點之和；頂點vi的入度的入度ID(vi)等于鄰接矩陣第等于鄰接矩陣第i列元素之和，即列元素之和，即： 對于無向圖，頂點對于無向圖，頂點v vi i的度等于鄰接矩陣第的度等于鄰接矩陣第i i行的元素之和，即：行的元素之和，即： njjiA1,njjiA1,njijA1,TDTD（v vi i）= = 對于帶權圖的鄰接矩陣，定義為：對于帶權圖的鄰接矩陣，定義為：Aij=Wij 若(vi,vj)或E，Wij 為該邊或弧的權

15、 反之2022-3-122 使用鄰接矩陣存儲結構，可用一維數(shù)組表示圖的頂點集合，使用鄰接矩陣存儲結構，可用一維數(shù)組表示圖的頂點集合，用二維數(shù)組表示圖的頂點之間關系（邊或?。┑募?，數(shù)據(jù)類型用二維數(shù)組表示圖的頂點之間關系（邊或?。┑募希瑪?shù)據(jù)類型定義如下：定義如下：#defineMAX_VERTEX_NUM20/最大頂點數(shù)最大頂點數(shù)typedefintAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣類型鄰接矩陣類型typedefstructVertexTypevexsMAX_VERTEX_NUM;/頂點表頂點表AdjMatrixarcs;/鄰接矩陣鄰接矩陣i

16、ntvexnum,arcnum;/圖的頂點數(shù)和弧數(shù)圖的頂點數(shù)和弧數(shù)MGraph; 由于一般圖的邊或弧較少，其鄰接矩陣的非零元素較少，屬稀由于一般圖的邊或弧較少，其鄰接矩陣的非零元素較少，屬稀疏矩陣，因此會造成一定存儲空間的浪費。疏矩陣，因此會造成一定存儲空間的浪費。2022-3-123 圖的鏈式存儲結構圖的鏈式存儲結構 1) 1) 為每個頂點建立一個單鏈表，為每個頂點建立一個單鏈表， 2) 2) 第第i i個單鏈表中包含頂點個單鏈表中包含頂點ViVi的所有鄰接頂點。的所有鄰接頂點。鄰接表是圖的一種鏈式存儲結構。鄰接表是圖的一種鏈式存儲結構。類似于樹的孩子鏈表表示類似于樹的孩子鏈表表示法。法。在

17、鄰接表中為圖中每個頂點建立一個單鏈表，在鄰接表中為圖中每個頂點建立一個單鏈表，用單鏈表中的用單鏈表中的一個結點表示依附于該頂點的一條邊一個結點表示依附于該頂點的一條邊（或表示以該頂點為弧尾的（或表示以該頂點為弧尾的一條?。?，稱為邊（或弧）結點。一條弧），稱為邊（或弧）結點。2022-3-124頭結點頭結點datafirstarc邊結點邊結點adjvexnextarcinfo2022-3-125(a)1304421302143231501234(b)41320212310123(c)14321300320123154320010101011001001110010011(a)(b)2022-3-

18、1262022-3-1272022-3-128(a)1304421302143231501234(b)41320212310123(c)143213003201231. 1. 區(qū)別：區(qū)別： 對于任一確定圖，鄰接矩陣是對于任一確定圖，鄰接矩陣是唯一唯一的（行列號與頂?shù)模ㄐ辛刑柵c頂點編號一致），但鄰接表點編號一致），但鄰接表不唯一不唯一（鏈接次序與頂點（鏈接次序與頂點編號無關）。編號無關）。 鄰接矩陣的空間復雜度為鄰接矩陣的空間復雜度為O(nO(n2 2),),而鄰接表的空間復而鄰接表的空間復雜度為雜度為O(n+e)O(n+e)。2. 2. 用途：用途：鄰接矩陣多用于鄰接矩陣多用于稠密圖稠密圖；而

19、鄰接表多用于；而鄰接表多用于稀稀疏圖疏圖鄰接矩陣與鄰接表表示法的關系鄰接矩陣與鄰接表表示法的關系2022-3-130圖的遍歷順序有兩種：圖的遍歷順序有兩種：對每種搜索順序，訪問各頂點的順序也不是唯一的。對每種搜索順序，訪問各頂點的順序也不是唯一的。深度優(yōu)先搜索深度優(yōu)先搜索depthfirstsearch廣度優(yōu)先搜索廣度優(yōu)先搜索breadthfirstsearch2022-3-1311深度優(yōu)先搜索思想深度優(yōu)先搜索思想深度優(yōu)先搜索遍歷類似于深度優(yōu)先搜索遍歷類似于樹的先序遍歷樹的先序遍歷。假定給定圖。假定給定圖G的初態(tài)是的初態(tài)是所有頂點均未被訪問過，在所有頂點均未被訪問過，在G中任選一個頂點中任選一

20、個頂點i作為遍歷的初始點，作為遍歷的初始點，則深度優(yōu)先搜索則深度優(yōu)先搜索遞歸調(diào)用包含以下操作：遞歸調(diào)用包含以下操作：（1 1）訪問搜索到的未被訪問的鄰接點；）訪問搜索到的未被訪問的鄰接點；（2 2）將此頂點的）將此頂點的visitedvisited數(shù)組元素值置數(shù)組元素值置1 1； （3 3）搜索該頂點的未被訪問的鄰接點，）搜索該頂點的未被訪問的鄰接點，若該鄰接點存在，則從此若該鄰接點存在，則從此鄰接點開始進行同樣的訪問和搜索。鄰接點開始進行同樣的訪問和搜索。深度優(yōu)先搜索深度優(yōu)先搜索DFSDFS可描述為：可描述為：（1 1）訪問）訪問v v0 0頂點；頂點；（2 2）置）置 visitedvvi

21、sitedv0 0=1=1；（3）搜索搜索v0未被訪問的鄰接點未被訪問的鄰接點w，若存在鄰接點若存在鄰接點w，則則DFS(w)。2022-3-1322022-3-133abchdekfgFFFFFFFFFT T T T T T T TTach d kfe bgachkfedbg訪問標志訪問標志: :訪問次序訪問次序: :例如例如:0123456782022-3-135intvisitedMAX_VERTEX_NUM;voidDFS(ALGraphG,intv)ArcNode*p;printf(%c,G.verticesv.data);visitedv=1;p=G.verticesv.first

22、arc;while(p)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-nextarc;/從第從第v個頂點出發(fā)個頂點出發(fā)DFS2022-3-136整個圖的整個圖的DFS遍歷遍歷voidDFSTraverse(ALGraphG)for(intv=0;vG.vexnum;+v)visitedv=0;for(v=0;vw1,V-w2,V-w8的路徑長度為的路徑長度為1；V-w7,V-w3,V-w5的路徑長度為的路徑長度為2；V-w6,V-w4的路徑長度為的路徑長度為3。w1Vw2w7w6w3w8w5w42022-3-1391廣度優(yōu)先搜索思想廣度優(yōu)先搜索思想設圖設圖G的

23、初態(tài)是所有頂點均未訪問，在的初態(tài)是所有頂點均未訪問，在G中任選一頂點中任選一頂點i作為初作為初始點，則廣度優(yōu)先搜索的基本思想是：始點，則廣度優(yōu)先搜索的基本思想是：并將其訪問標志置為已并將其訪問標志置為已被訪問，即被訪問，即visitedi=1；依此類推，直到圖中所有頂點都被訪問完為止依此類推，直到圖中所有頂點都被訪問完為止。2022-3-140廣度優(yōu)先搜索在搜索訪問一層時，需要記住已被訪問的頂點，廣度優(yōu)先搜索在搜索訪問一層時，需要記住已被訪問的頂點，以便在訪問下層頂點時，從已被訪問的頂點出發(fā)搜索訪問其鄰接以便在訪問下層頂點時，從已被訪問的頂點出發(fā)搜索訪問其鄰接點。所以在廣度優(yōu)先搜索點。所以在廣

24、度優(yōu)先搜索中中需要設置一個隊列需要設置一個隊列Queue，使已被訪使已被訪問的頂點順序由隊尾進入隊列。在搜索訪問下層頂點時，先從隊問的頂點順序由隊尾進入隊列。在搜索訪問下層頂點時，先從隊首取出一個已被訪問的上層頂點，再從該頂點出發(fā)搜索訪問它的首取出一個已被訪問的上層頂點，再從該頂點出發(fā)搜索訪問它的各個鄰接點各個鄰接點 2022-3a)2022-3a)17823456(b)17823456(c)2022-3-143u按照生成樹的定義，按照生成樹的定義，n 個頂點的連通網(wǎng)絡的生成樹有個頂點的連通網(wǎng)絡的生成樹有n 個頂點、個頂點、n- -1條邊條邊

25、。而所有包含而所有包含n-1 n-1 條邊及條邊及n n個頂點的個頂點的連通圖都是無回路的樹，所以生成樹是連通圖中的極連通圖都是無回路的樹，所以生成樹是連通圖中的極小連通子圖小連通子圖. .u在圖論中，常常將在圖論中，常常將樹定義為一個無回路連通圖樹定義為一個無回路連通圖。u 對于一個帶權的無向連通圖，把所有邊上權值之和最對于一個帶權的無向連通圖，把所有邊上權值之和最小的生成樹稱為圖的小的生成樹稱為圖的最小生成樹最小生成樹。u求圖的最小生成樹有很多實際應用。例如，通訊線路求圖的最小生成樹有很多實際應用。例如，通訊線路鋪設造價最優(yōu)問題就是一個最小生成樹問題。鋪設造價最優(yōu)問題就是一個最小生成樹問題

26、。 2022年3月1日 v必須只使用該必須只使用該網(wǎng)中的邊網(wǎng)中的邊來構造最小生成樹；來構造最小生成樹；v必須使用且僅使用必須使用且僅使用n-1n-1條邊條邊來聯(lián)結網(wǎng)絡中的來聯(lián)結網(wǎng)絡中的n n個個頂點頂點v不能使用產(chǎn)生不能使用產(chǎn)生回路回路的邊的邊構造最小生成樹的準則構造最小生成樹的準則(連通網(wǎng)的連通網(wǎng)的)最小生成樹最小生成樹假設要在假設要在n 個城市之間建立通訊個城市之間建立通訊聯(lián)絡網(wǎng)，則連通聯(lián)絡網(wǎng)，則連通n 個城市只需要修建個城市只需要修建n-1條線路，條線路，如何在最節(jié)省經(jīng)費的前如何在最節(jié)省經(jīng)費的前提下建立提下建立這個這個通訊網(wǎng)通訊網(wǎng)？問題：問題：2022-3-146下面分別介紹下面分別介紹

27、克魯斯卡爾克魯斯卡爾( (Kruskal)Kruskal)算法和普里姆算法和普里姆( (Prim)Prim)算法算法。 克魯斯卡爾算法是克魯斯卡爾算法是一種按權值遞增的次序選擇合適的邊來一種按權值遞增的次序選擇合適的邊來構造最小生成樹的方法。構造最小生成樹的方法。v必須只使用該必須只使用該網(wǎng)中的邊網(wǎng)中的邊來構造最小生成樹；來構造最小生成樹；v必須使用且僅使用必須使用且僅使用n-1n-1條邊條邊來聯(lián)結網(wǎng)絡中的來聯(lián)結網(wǎng)絡中的n n個個頂點頂點v不能使用產(chǎn)生不能使用產(chǎn)生回路回路的邊的邊構造最小生成樹的準則構造最小生成樹的準則2022-3-147假設假設G=G=（V V，E E）是一個具有是一個具有n

28、 n個頂點的帶權無向連通圖，個頂點的帶權無向連通圖，T= (UT= (U，TE)TE)是是G G的最小生成樹，其中的最小生成樹，其中U U是是T T的頂點集，的頂點集，TETE是是T T的邊集，則構造的邊集，則構造最小生成樹的過程如下：最小生成樹的過程如下：(1) (1) 置置U U的初值等于的初值等于V V，TETE的初值為空集；的初值為空集；(2) (2) 按權值從小到大的順序依次選取圖按權值從小到大的順序依次選取圖G G中的邊，若選取的邊未使中的邊，若選取的邊未使生成樹生成樹T T形成回路，則加入形成回路，則加入TETE；若選取的邊使生成樹若選取的邊使生成樹T T形成回路，形成回路，則將

29、其舍棄。循環(huán)執(zhí)行則將其舍棄。循環(huán)執(zhí)行(2)(2)，直到，直到TETE中包含中包含( (n-1)n-1)條邊為止。條邊為止。 2022-3-1482022-3-149為實現(xiàn)克魯斯卡爾算法需要設置一維輔助數(shù)組為實現(xiàn)克魯斯卡爾算法需要設置一維輔助數(shù)組E E，按權值從小到大按權值從小到大的順序存放圖的邊，數(shù)組的下標取值從的順序存放圖的邊，數(shù)組的下標取值從0 0到到e-1e-1（e e為圖為圖G G邊的數(shù)邊的數(shù)目）。目）。 假設數(shù)組假設數(shù)組E E存放圖存放圖G G中的所有邊，且邊已按權值從小到大的順序排中的所有邊，且邊已按權值從小到大的順序排列。列。n n為圖為圖G G的頂點個數(shù)，的頂點個數(shù)，e e為圖

30、為圖G G的邊數(shù)?？唆斔箍査惴ㄈ缦拢旱倪厰?shù)?？唆斔箍査惴ㄈ缦拢?define MAXE #define MAXV typedef struct int vex1; /邊的起始頂點邊的起始頂點int vex2; /邊的終止頂點邊的終止頂點int weight; /邊的權值邊的權值Edge; 2022-3-1507.4.2普里姆普里姆(Prim)算法算法普里姆算法的基本思想：普里姆算法的基本思想：按逐個將頂點連通的方式來構按逐個將頂點連通的方式來構造最小生成樹的。造最小生成樹的。從連通網(wǎng)絡從連通網(wǎng)絡N=V,E中的某一頂點中的某一頂點u0出發(fā)，選擇與出發(fā)，選擇與它關聯(lián)的具有最小權值的邊它關聯(lián)的具

31、有最小權值的邊(u0,v)，將其頂點加入到生成樹將其頂點加入到生成樹的頂點集合的頂點集合U中。中。以后每一步從一個頂點在以后每一步從一個頂點在U中，而另一個中，而另一個頂點不在頂點不在U中的各條邊中選擇權值最小的邊中的各條邊中選擇權值最小的邊(u,v),把該邊加把該邊加入到生成樹的邊集入到生成樹的邊集TE中，把它的頂點加入到集合中，把它的頂點加入到集合U中。如中。如此重復執(zhí)行，直到網(wǎng)絡中的所有頂點都加入到生成樹頂點此重復執(zhí)行，直到網(wǎng)絡中的所有頂點都加入到生成樹頂點集合集合U中為止。中為止。在生成樹的構造過程中，圖中在生成樹的構造過程中，圖中n個個頂點分屬兩個集合：頂點分屬兩個集合：已落在生成樹

32、上的已落在生成樹上的頂點集頂點集U和尚未落在生成樹上的頂點集和尚未落在生成樹上的頂點集V-U，則應在所有連通，則應在所有連通U中頂點和中頂點和V-U中中頂點的邊中選取權值最小的邊。頂點的邊中選取權值最小的邊。一般情況下所添加的頂點應滿足下列一般情況下所添加的頂點應滿足下列條件條件:2022-3-152假設假設G=(VG=(V，E)E)是一個具有是一個具有n n個頂點的帶權無向連通圖，個頂點的帶權無向連通圖，T(UT(U，TE)TE)是是G G的最小生成樹，其中的最小生成樹，其中U U是是T T的頂點集，的頂點集，TETE是是T T的邊的邊集，則構造集，則構造G G的最小生成樹的最小生成樹T T

33、的步驟如下：的步驟如下： （1 1）初始狀態(tài)，）初始狀態(tài)，TETE為空，為空，U=vU=v0 0 ，v v0 0VV； （2 2）在所有在所有uUuU，vV-UvV-U的邊的邊( (u u，v) Ev) E中找一條代價中找一條代價最小的邊最小的邊( (uu，v)v)并入并入TETE，同時將同時將vv并入并入U U；重復執(zhí)行步驟（重復執(zhí)行步驟（2 2）n-1n-1次，直到次，直到U=VU=V為止。為止。為了便于在集合為了便于在集合U U和和( (V-U)V-U)之間選取權值最小的邊，需要設置之間選取權值最小的邊，需要設置兩個輔助數(shù)組兩個輔助數(shù)組closestclosest和和lowcostlow

34、cost，分別用于存放頂點的序號分別用于存放頂點的序號和邊的權值。和邊的權值。 設置兩個輔助數(shù)組，對當前設置兩個輔助數(shù)組，對當前VU集中的每個頂點，記錄和頂集中的每個頂點，記錄和頂點集點集U中頂點相連接的代價最小的邊：中頂點相連接的代價最小的邊：對于每一個頂點對于每一個頂點vV-UvV-U，closestvclosestv為為U U中距離中距離v v最近的一個鄰接最近的一個鄰接點，即邊點，即邊 ( (v v，closestv) closestv) 是在所有與頂點是在所有與頂點v v相鄰、且其另一頂相鄰、且其另一頂點點jUjU的邊中具有最小權值的邊，其最小權值為的邊中具有最小權值的邊，其最小權值

35、為lowcostvlowcostv，即即intclosestMAX_VERTEX_NUM;/U集中的頂點序號集中的頂點序號intlowcostMAX_VERTEX_NUM;/邊的權值邊的權值abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c5 5普里姆算法普里姆算法克魯斯卡爾算法克魯斯卡爾算法時間復雜度時間復雜度O(n2)O(eloge)歸并頂點歸并頂點稠密圖稠密圖歸并邊歸并邊稀疏圖稀疏圖算法名算法名適應范圍適應范圍比較兩種算法比較兩種算法2022-3-156 交通網(wǎng)絡中常常提出這樣的問題：從甲地到乙交通網(wǎng)絡中常常提

36、出這樣的問題：從甲地到乙地之間是否有公路連通地之間是否有公路連通? ? 在有多條通路的情況下，在有多條通路的情況下，哪一條路最短哪一條路最短? ? 兩點之間的最短路徑問題兩點之間的最短路徑問題2022-3-157交通網(wǎng)絡可用帶權圖來表示交通網(wǎng)絡可用帶權圖來表示 1) 1)最少換乘（經(jīng)過的頂點數(shù)最少）最少換乘（經(jīng)過的頂點數(shù)最少） -BFS -BFS算法算法 2 2）路徑最短（權值之和最?。┞窂阶疃蹋嘀抵妥钚。?邊上邊上權權值可表示兩城市之間的距離、交通費值可表示兩城市之間的距離、交通費或途中所花費的時間等。求兩個頂點之間的最短或途中所花費的時間等。求兩個頂點之間的最短路徑，是指路徑上各邊的路

37、徑，是指路徑上各邊的權值之和最小權值之和最小。并假定。并假定討論的權值不能為負數(shù)。討論的權值不能為負數(shù)。7.5最短路徑問題最短路徑問題2022-3-158最短路徑：最短路徑：如果從圖中某一頂點如果從圖中某一頂點(稱為源點稱為源點)到達另一到達另一頂點頂點(稱為終點稱為終點)的路徑可能不止一條，如何的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權值找到一條路徑使得沿此路徑上各邊上的權值總和達到最小?？偤瓦_到最小。 對于對于帶權帶權的圖，通常把一條路徑上所經(jīng)的圖，通常把一條路徑上所經(jīng)過過邊或弧上的邊或弧上的權值之和權值之和定義為該路徑的路徑定義為該路徑的路徑長度長度。從一個頂點到另一個

38、頂點可能存在著。從一個頂點到另一個頂點可能存在著多條路徑，把路徑長度最短的那條路徑稱為多條路徑，把路徑長度最短的那條路徑稱為最短路徑最短路徑，其路徑長度稱為最短路徑長度。，其路徑長度稱為最短路徑長度。 2022-3-1597.5.1求從某個源點到其余各點的求從某個源點到其余各點的最短路徑最短路徑7.5.2每一對頂點之間的最短路徑每一對頂點之間的最短路徑本節(jié)討論兩種最常見的最短路徑問題本節(jié)討論兩種最常見的最短路徑問題求求從源點到其余各點的最短路徑從源點到其余各點的最短路徑的算法的基本思想的算法的基本思想:依依最短路徑的長度最短路徑的長度遞增的次序求得遞增的次序求得各條路徑各條路徑源點源點v1其中

39、，從源點到其中，從源點到頂點頂點v的最短路徑的最短路徑是所有最短路徑是所有最短路徑中長度最短者。中長度最短者。v2在這條路徑上，在這條路徑上，必定只含一條弧必定只含一條弧，并且，并且這條弧的這條弧的權值最小。權值最小。下一條下一條路徑長度次短路徑長度次短的最短路徑的特點：的最短路徑的特點：路徑長度最短路徑長度最短的最短路徑的特點：的最短路徑的特點：它只可能有兩種情況：或者是它只可能有兩種情況：或者是直接從源直接從源點到該點點到該點(只含一條弧只含一條弧)；或者是或者是從源點經(jīng)從源點經(jīng)過頂點過頂點v1，再到達該頂點，再到達該頂點(由兩條弧組成由兩條弧組成)。其余最短路徑的特點：其余最短路徑的特點

40、：再下一條再下一條路徑長度次短路徑長度次短的最短路徑的特點的最短路徑的特點:它可能有三種情況：或者是它可能有三種情況：或者是直接從源點到直接從源點到該點該點(只含一條弧只含一條弧)；或者是或者是從源點經(jīng)過頂從源點經(jīng)過頂點點v1，再到達該頂點，再到達該頂點(由兩條弧組成由兩條弧組成)；或者；或者是從源點經(jīng)過頂點是從源點經(jīng)過頂點v2，再到達該頂點。，再到達該頂點。它或者是它或者是直接從源點到該點直接從源點到該點(只含一條只含一條弧弧)；或者是或者是從源點經(jīng)過已求得最短路徑從源點經(jīng)過已求得最短路徑的頂點，再到達該頂點的頂點，再到達該頂點。求最短路徑的迪杰斯特拉算法：求最短路徑的迪杰斯特拉算法：一般情

41、況下，一般情況下，Distk=或者或者=+。 設置輔助數(shù)組設置輔助數(shù)組Dist，其中每個分量，其中每個分量Distk表示表示當前所求得的從源點到其余各頂點當前所求得的從源點到其余各頂點k的最短路徑。的最短路徑。1）在所有從源點出發(fā)的弧中選取一條權）在所有從源點出發(fā)的弧中選取一條權值最小的弧，即為第一條最短路徑。值最小的弧，即為第一條最短路徑。2）修改其它各頂點的）修改其它各頂點的Distk值。值。假設求得最短路徑的頂點為假設求得最短路徑的頂點為u，若若Distu+G.arcsukDistk則將則將Distk改為改為Distu+G.arcsuk。INFINITYkvarcsGkDist0.V0和

42、和k之間存在弧之間存在弧V0和和k之間不存在弧之間不存在弧其中的最小值即為最短路徑的長度。其中的最小值即為最短路徑的長度。2022-3-165算法的基本思想是算法的基本思想是: :設置并逐步擴充一個集合設置并逐步擴充一個集合S S，存放已求出存放已求出其最短路徑的頂點，則尚未確定最短路徑的頂點集合是其最短路徑的頂點，則尚未確定最短路徑的頂點集合是V-SV-S，其中其中V V為網(wǎng)中所有頂點集合。按最短路徑長度遞增的順序逐個為網(wǎng)中所有頂點集合。按最短路徑長度遞增的順序逐個以以V-SV-S中的頂點加到中的頂點加到S S中，直到中，直到S S中包含全部頂點，而中包含全部頂點，而V-SV-S為空。為空。

43、2022-3-166圖圖7-16帶權有向圖帶權有向圖 53204110010205051030602022-3-167從以上圖從以上圖7-167-16的最短路徑可以看出：的最短路徑可以看出：(1) (1) 最短路徑并不一定是經(jīng)過邊或弧數(shù)最少的路徑。如從頂點最短路徑并不一定是經(jīng)過邊或弧數(shù)最少的路徑。如從頂點0 0到頂?shù)巾旤c點5 5的路徑（的路徑（0 0，5 5）長度為）長度為100100，路徑（，路徑（0 0，4 4，5 5）長度為）長度為9090，路徑，路徑（0 0，2 2，3 3，5 5）長度為）長度為7070，路徑（，路徑（0 0，4 4，3 3，5 5）長度為）長度為6060，其中最，其

44、中最短路徑為（短路徑為（0 0，4 4，3 3，5 5），最短路徑長度為），最短路徑長度為6060。(2) (2) 這些最短路徑中，長度最短的路徑上只有一條弧，且它的權值這些最短路徑中，長度最短的路徑上只有一條弧，且它的權值在從源點出發(fā)的所有弧的權值中最小。如從源點在從源點出發(fā)的所有弧的權值中最小。如從源點0 0出發(fā)有出發(fā)有3 3條弧，其條弧，其中以弧中以弧02的權值為最小。此時（的權值為最小。此時（0 0，2 2）不僅是頂點）不僅是頂點 0 0到頂點到頂點2 2 的一條最短路徑，而且它在從源點的一條最短路徑，而且它在從源點0 0到其它各頂點的最短路徑中長度到其它各頂點的最短路徑中長度最短。最

45、短。 (3) (3)按照路徑長度遞增的次序產(chǎn)生最短路徑。求得第二條最短路徑按照路徑長度遞增的次序產(chǎn)生最短路徑。求得第二條最短路徑（0 0，4 4）；之后求得第三條最短路徑（）；之后求得第三條最短路徑（0 0，4 4，3 3），它經(jīng)過已求出的），它經(jīng)過已求出的第二條最短路徑（第二條最短路徑（0 0，4 4）到達頂點）到達頂點3 3；求得的第四條最短路徑（；求得的第四條最短路徑（0 0，4 4，3 3，5 5），經(jīng)過已求出的第三條最短路徑（），經(jīng)過已求出的第三條最短路徑（0 0，4 4，3 3）到達頂點）到達頂點5 5。 2022-3-168迪杰斯特拉算法的求解過程：迪杰斯特拉算法的求解過程： 1

46、0 3 5 20 8 25 4 30 3 30 1 2 3 5 4 (a) 一個有向網(wǎng)點 (b) 源點 1 到其它頂點的初始距離 1 2 3 5 4 12 3 8 25 30 1 2 3 5 4 (c) 第一次求得的結果 (d) 第二次求得的結果 3 8 12 4 1 2 3 5 4 2022-3-169 3 8 12 4 3 8 12 4 (e) 第三次求得的結果 (f) 第四次求得的結果 1 2 3 5 4 1 2 3 5 4 圖圖7-17迪杰斯特拉算法求最短路徑過程及結果迪杰斯特拉算法求最短路徑過程及結果2022-3-171 在狄克斯特拉算法中，求一條最短路徑所花費的時間：從在狄克斯特拉

47、算法中，求一條最短路徑所花費的時間：從V-S中選取具有最小距離的頂點中選取具有最小距離的頂點vk花費時間花費時間O(n)；修改修改V-S中頂點的距中頂點的距離花費時間離花費時間O(n)；輸出最短路徑花費時間輸出最短路徑花費時間O(n)。因此求出因此求出n-1條最條最短路徑的時間復雜度為短路徑的時間復雜度為O(n2)。2022-3-172 頂點對之間的最短路徑是指：對于給定的有向頂點對之間的最短路徑是指：對于給定的有向網(wǎng)網(wǎng)G=(V,E),G=(V,E),要對要對G G中任意一對頂點有序對中任意一對頂點有序對V V、W(VW),W(VW),找出找出V V到到W W的最短距離和的最短距離和W W到到

48、V V的最短距離。的最短距離。 解決此問題的一個有效方法是解決此問題的一個有效方法是: :輪流以每一個頂輪流以每一個頂點為源點點為源點, ,重復執(zhí)行迪杰斯特拉算法重復執(zhí)行迪杰斯特拉算法n n次次, ,即可求得每即可求得每一對頂點之間的最短路徑一對頂點之間的最短路徑, ,總的時間復雜度為總的時間復雜度為O(nO(n3 3) )。 弗洛伊德提出了另外一個求圖中任意兩頂點之弗洛伊德提出了另外一個求圖中任意兩頂點之間最短路徑的算法，雖然其時間復雜度也是間最短路徑的算法，雖然其時間復雜度也是 O(nO(n3 3) )，但其算法的形式更簡單，易于理解和編程。但其算法的形式更簡單，易于理解和編程。求每一對頂

49、點之間的最短路徑求每一對頂點之間的最短路徑弗洛伊德算法弗洛伊德算法(Floyd)的基本思想是：的基本思想是： 從從 v vi i 到到 v vj j 的所有的所有可能存在的路徑中，選可能存在的路徑中，選出一條長度最短的路徑出一條長度最短的路徑。若若存在，則存在路徑存在，則存在路徑vi,vj/路徑中不含其它頂點路徑中不含其它頂點若若,存在，則存在路徑存在，則存在路徑vi,v1,vj/路徑中所含頂點序號不大于路徑中所含頂點序號不大于1若若vi,v2,v2,vj存在，存在，則存在一條路徑則存在一條路徑vi,v2,vj/路徑中所含頂點序號不大于路徑中所含頂點序號不大于2依次類推，則依次類推，則vi至至

50、vj的最短路徑應是的最短路徑應是上述這些路徑中，路徑長度最小者。上述這些路徑中，路徑長度最小者。2022-3-175 弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣arcsn+1n+1arcsn+1n+1來存儲帶權有向圖。算法的基本思想是來存儲帶權有向圖。算法的基本思想是: :設設置一個置一個nxnnxn的矩陣的矩陣A A(k)(k)，其中除對角線的元素都等于其中除對角線的元素都等于0 0外，其外，其它元素它元素a a(k)(k)ijij表示頂點表示頂點i i到頂點到頂點j j的路徑長度，的路徑長度，K K表示運算表示運算步驟。開始時，以任意兩個頂點之間的

51、有向邊的權值作為路步驟。開始時，以任意兩個頂點之間的有向邊的權值作為路徑長度，沒有有向邊時，路徑長度為徑長度，沒有有向邊時，路徑長度為，當，當K=OK=O時時, , A A (0)(0)ij=arcsijij=arcsij 以后逐步嘗試在原路徑中加入其它頂點作為中間頂點，以后逐步嘗試在原路徑中加入其它頂點作為中間頂點，如果增加中間頂點后，得到的路徑比原來的路徑長度減少了，如果增加中間頂點后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為：則以此新路徑代替原路徑，修改矩陣元素。具體做法為： 2022-3-176 第一步，讓所有邊上加入中間頂點第一步，讓所有邊上

52、加入中間頂點1 1，取，取AijAij與與Ai1+A1jAi1+A1j中較小的值作中較小的值作AijAij的值，完成后得到的值，完成后得到A A(1)(1)， 第二步，讓所有邊上加入中間頂點第二步，讓所有邊上加入中間頂點2 2，取，取AijAij與與Ai2+A2jAi2+A2j中較小的值，完成后得到中較小的值，完成后得到A A(2)(2)，如此進行下去，如此進行下去，當?shù)诋數(shù)趎 n步完成后，得到步完成后，得到A A(n)(n)，A A(n)(n)即為我們所求結果即為我們所求結果, ,A A(n)(n)ijij表示表示頂點頂點i i到頂點到頂點j j的最短距離。的最短距離。 因此，弗洛伊德算法可

53、以描述為因此，弗洛伊德算法可以描述為:A(0)ij=arcsij;/arcs為圖的鄰接矩陣為圖的鄰接矩陣A(k)ij=minA(k-1)ij,A(k-1)ik+A(k-1)kj其中其中k=1,2,n2022-3-1772022-3-179通常我們把計劃、施工過程、生產(chǎn)流程、程序流程等都當成通常我們把計劃、施工過程、生產(chǎn)流程、程序流程等都當成一個工程，一個大的工程常常被劃分成許多較小的子工程，這一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動。這些活動完成時，整個工程也就完成了。些子工程稱為活動。這些活動完成時，整個工程也就完成了。 例如，計算機專業(yè)學生的課程開設可看成是一

54、個工程，每一例如，計算機專業(yè)學生的課程開設可看成是一個工程，每一門課程就是工程中的活動，圖門課程就是工程中的活動，圖7-217-21給出了若干門所開設的課程，給出了若干門所開設的課程，其中有些課程的開設有先后關系，有些則沒有先后關系，有先其中有些課程的開設有先后關系，有些則沒有先后關系，有先后關系的課程必須按先后關系開設，如開設數(shù)據(jù)結構課程之前后關系的課程必須按先后關系開設，如開設數(shù)據(jù)結構課程之前必須先學完程序設計基礎及離散數(shù)學，而開設離散數(shù)學則必須必須先學完程序設計基礎及離散數(shù)學，而開設離散數(shù)學則必須先并行學完高等數(shù)學、程序設計基礎課程。先并行學完高等數(shù)學、程序設計基礎課程。2022-3-1

55、80課程代號 課程名稱 先修課程 Cl 高等數(shù)學 無 C2 程序語言 無 C3 離散數(shù)學 C1 C4 數(shù)據(jù)結構 C2，C3 C5 編譯原理 C2，C4 C6 操作系統(tǒng) C4，C7 C7 計算機組成原理 C2圖圖7-22 7-22 課程安排的課程安排的AOVAOV網(wǎng)網(wǎng)C1C7C2C5C4C3C6在圖在圖7-227-22中，我們用一中，我們用一種有向圖來表示課程開種有向圖來表示課程開設，在這種有向圖中，設，在這種有向圖中，頂點表示活動，有向邊頂點表示活動，有向邊表示活動的優(yōu)先關系，表示活動的優(yōu)先關系，這有向圖叫做頂點表示這有向圖叫做頂點表示活動的網(wǎng)絡活動的網(wǎng)絡( (Actire On Actire

56、 On Vertices)Vertices)簡稱為簡稱為。2022-3-181拓撲排序：拓撲排序： 假設假設G=(VG=(V，E)E)是一個具有是一個具有n n個頂點的有向圖，個頂點的有向圖，V V中頂點序列中頂點序列v vl l，v v2 2，v vn n稱做一個拓撲序列稱做一個拓撲序列( (Topological Order)Topological Order)，當且僅當當且僅當該頂點序列滿足下列條件：若在有向圖該頂點序列滿足下列條件：若在有向圖G G中存在從頂點中存在從頂點v vi i到到v vj j的的一條路徑，則在頂點序列中頂點一條路徑，則在頂點序列中頂點v vi i必須排在頂點必須

57、排在頂點v vj j之前。通常，之前。通常，在在AOVAOV網(wǎng)中，網(wǎng)中，將所有活動排列成一個拓撲序列的過程叫做將所有活動排列成一個拓撲序列的過程叫做拓撲排拓撲排序序( (Topological Sort)Topological Sort)。何謂何謂“拓撲排序拓撲排序”？對有向圖進行如下操作：對有向圖進行如下操作：按照有向圖給出的次序關系，按照有向圖給出的次序關系，將圖中頂點排成一個線性序列，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關對于有向圖中沒有限定次序關系的頂點，則可以人為加上任系的頂點，則可以人為加上任意的次序關系。意的次序關系。例如：對于下列有向圖例如：對于下列有向圖BDA

58、C可求得可求得拓撲有序序列拓撲有序序列：ABCD或或ACBD由此所得頂點的線性序列稱之為由此所得頂點的線性序列稱之為拓撲有序序列拓撲有序序列BDAC反之，對于下列有向圖反之，對于下列有向圖不能求得它的拓撲有序序列。不能求得它的拓撲有序序列。因為圖中存在一個回路因為圖中存在一個回路B,C,D2022-3-185 由于由于AOVAOV網(wǎng)中有些活動之間沒有次序要求，它們在拓撲序網(wǎng)中有些活動之間沒有次序要求，它們在拓撲序列的位置可以是任意的，因此列的位置可以是任意的，因此拓撲排序的結果不唯一拓撲排序的結果不唯一。學生按照任何一個拓撲序列都可以完成所要求的全部課程學生按照任何一個拓撲序列都可以完成所要求

59、的全部課程學習。學習。 在在AOVAOV網(wǎng)中不應該出現(xiàn)有向環(huán)。因為環(huán)的存在意味著某網(wǎng)中不應該出現(xiàn)有向環(huán)。因為環(huán)的存在意味著某項活動將以自己為先決條件，顯然無法形成拓撲序列。項活動將以自己為先決條件，顯然無法形成拓撲序列。 判定網(wǎng)中是否存在環(huán)的方法：判定網(wǎng)中是否存在環(huán)的方法：對有向圖構造其頂點的拓撲對有向圖構造其頂點的拓撲有序序列有序序列，若網(wǎng)中所有頂點都出現(xiàn)在它的拓撲有序序列中，若網(wǎng)中所有頂點都出現(xiàn)在它的拓撲有序序列中，則該則該AOVAOV網(wǎng)中一定不存在環(huán)。網(wǎng)中一定不存在環(huán)。無向圖中是否存在環(huán)的判定方法？無向圖中是否存在環(huán)的判定方法？ (DFS)(DFS)如何進行拓撲排序？如何進行拓撲排序？一、從有向圖中選取一個沒有前驅一、從有向圖中選取一個沒有前驅的頂點，并輸出之；的頂點，并輸出之；重復上述兩步，直至圖空，或者重復上述兩步，直至圖空，或者圖不空但找不到無前驅的頂點為止圖不空但找不到無前驅的頂點為止。二、從有向圖中刪去此頂點以及所二、從有向圖中刪去此頂點以及所有以它為尾的??；有以它為尾的?。籥bcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念沒有前驅的頂點沒有前驅的頂點入度為零的頂點入度為零的頂點刪除頂點及以它為尾的弧刪除頂點及以它為尾的弧弧頭頂點的入度減弧頭頂點的入度減12022-3-1