數(shù)據(jù)結(jié)構(gòu)與算法第六章課件

1、第6章 圖6.1 圖的基本概念6.2 圖的存儲結(jié)構(gòu)6.3 圖的遍歷6.4 無向圖的應(yīng)用6.5 有向圖的應(yīng)用6.6 最短路徑6.1 圖的基本概念圖 圖是由頂點集合 V 及頂點間的關(guān)系集合 E 所組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph 其中： V=x|x某個數(shù)據(jù)對象 是非空的有限頂點集合； E=(x, y) | x, y V /邊(Edge)的集合 或 E= | x, y V /弧(Arc)的集合 是頂點之間關(guān)系的有限集合。在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結(jié)點個數(shù)可以為零，稱為空樹；在圖中，頂點個數(shù)不能為零，但可以沒有邊。6.1 圖的基本概念無向圖無向圖 G 是由兩個集合 V(G) 和

2、E(G) 組成的 其中：V(G) 是頂點的非空有限集； E(G) 是邊的有限集合，邊是頂點的無序?qū)Γ洖椋╲,w）或（w,v)，并且（v,w)=(w,v)有向圖有向圖 G 是由兩個集合 V(G) 和 E(G) 組成的 其中：V(G) 是頂點的非空有限集； E(G) 是有向邊（也稱弧）的有限集合，弧是頂點的有序?qū)?，記為，v, w是頂點，v 為弧尾(或始點)，w 為弧頭(終點)， 。6.1 圖的基本概念例無向圖G1V(G1)=1,2,3,4,5,6,7E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)有向圖G2V(G2)=1,2,3,4,5,6

3、 E(G2)=, , , , , , 245136G2157324G166.1 圖的基本概念圖的抽象數(shù)據(jù)類型class Graph public: Graph ( ); /建立一個空圖 void InsertVertex ( Type & vertex ); void InsertEdge (int v1, int v2 ); void RemoveVertex ( int v ); void RemoveEdge ( int v1, int v2 ); int IsEmpty ( ); Type GetWeight ( int v1, int v2 ); int GetFirstNeighb

4、or ( int v ); int GetNextNeighbor ( int v1, int v2 );6.1 圖的基本概念圖的術(shù)語鄰接點（或相鄰點，關(guān)聯(lián)）如果 e=(u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接點或相鄰點；稱邊 e 與頂點 u ,v 關(guān)聯(lián)；如果 a= 是 E(G) 中的一條弧，則稱 u 鄰接到v 或 v 鄰接于 u；稱弧 a 與頂點u , v關(guān)聯(lián)。在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系；在樹結(jié)構(gòu)中，結(jié)點之間具有層次關(guān)系；在圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系。 FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比在

5、線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼；在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系為雙親和孩子；在圖結(jié)構(gòu)中，頂點之間的關(guān)系為鄰接。 FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比6.1 圖的基本概念圖的術(shù)語權(quán)與圖的邊或弧相關(guān)的數(shù)。網(wǎng)帶權(quán)的無向圖稱為無向網(wǎng)；帶權(quán)的有向圖稱為有向網(wǎng)。有向網(wǎng)無向網(wǎng)6.1 圖的基本概念圖的術(shù)語頂點的度（與樹中結(jié)點的度不同）無向圖中，頂點的度是與每個頂點關(guān)聯(lián)的邊數(shù)，記作 TD(v)。有向圖中，頂點的度分成入度與出度入度：以該頂點為終頭的弧的數(shù)目，記為 ID(v)出度：以該頂點為始點的弧的數(shù)目，記為 OD(v)一個頂點的度等于該頂點的入度與出度之

6、和，即TD(v)=OD(v)+ID(v)6.1 圖的基本概念圖的術(shù)語自環(huán)稱邊 (v, v)E(G) 或弧 E(G)為自環(huán) 多重邊（或?。┤粼?G 中有兩條或兩條以上相同的邊或弧，稱之為多重邊（或弧）6.1 圖的基本概念圖的術(shù)語簡單圖圖中不含有自環(huán)和多重邊（或?。┑膱D稱為簡單圖，否則稱為非簡單圖。本章只討論簡單圖，即有兩類圖形不在本章討論之列6.1 圖的基本概念圖的術(shù)語完全圖 若有 n 個頂點的無向圖有 n(n-1)/2 條邊，則此圖為完全無向圖。若有 n 個頂點的有向圖有n(n-1) 條邊，則此圖為完全有向圖。稀疏圖（sparse graph）邊或弧很少的圖，通常邊數(shù) enlog2n稠密圖（D

7、ense graph）無向圖中，邊數(shù)接近n(n-1)/2 ；有向圖中，弧數(shù)接近n(n-1)。6.1 圖的基本概念圖的術(shù)語路徑在圖 G 中，頂點序列(vi1, vi2, ,vim) 且(vij,vij+1)E 或 E ，j=1, 2, , m-1，則稱此序列為從頂點 vi1 到頂點vim的一條路徑。頂點 vi1 稱為始點；頂點vim 稱為終點?；芈肥键c和終點相同的路徑。6.1 圖的基本概念圖的術(shù)語簡單路徑序列中頂點不重復(fù)出現(xiàn)的路徑。簡單回路始點和終點相同的簡單路徑。6.1 圖的基本概念圖的術(shù)語路徑長度 無權(quán)圖的路徑長度是指此路徑上邊（或?。┑臈l數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊（或弧）的權(quán)之和。

8、6.1 圖的基本概念圖的術(shù)語子圖已知圖 G(V, E) 和圖 G(V, E)。若VV 且 EE，則稱 G 為 G 的子圖。6.1 圖的基本概念圖的術(shù)語連通圖在無向圖中， 若從頂點v1到頂點v2有路徑，則稱頂點v1與v2是連通的。圖中任意兩個頂點都連通的無向圖稱為連通圖。連通分量非連通圖中極大連通子圖稱做連通分量。1.含有極大頂點數(shù)；2.依附于這些頂點的所有邊。6.1 圖的基本概念圖的術(shù)語例ABCDEFGIJLHMKABCDEHMFGIJLK3個連通分量 6.1 圖的基本概念圖的術(shù)語強連通圖與強連通分量在有向圖中，若對于每一對頂點 vi 和 vj，都存在一條從 vi 到 vj 和從 vj 到 v

9、i 的有向路徑，則稱此圖是強連通圖。非強連通圖的極大強連通子圖稱做強連通分量。V1V2V3V4V1V3V4V22個強連通分量 6.1 圖的基本概念圖的術(shù)語生成樹n個頂點的連通圖的生成樹是包含圖中全部 n 個頂點的一個極小連通子圖；ABCDEHM無向圖G ABCDEHM無向圖G的生成樹 多構(gòu)成回路少不連通含有n-1條邊6.1 圖的基本概念圖的術(shù)語生成森林由若干棵生成樹組成，含全部頂點，但構(gòu)成這些樹的邊是最少的。FGIJLK生成森林ABCDEFGIJLHMK無向圖GABCDEHM6.2 圖的存儲結(jié)構(gòu)是否可以采用順序存儲結(jié)構(gòu)存儲圖?圖的特點：頂點之間的關(guān)系是m:n，即任何兩個頂點之間都可能存在關(guān)系（

10、邊），無法通過存儲位置表示這種任意的邏輯關(guān)系，所以，圖無法采用順序存儲結(jié)構(gòu)。如何存儲圖?考慮圖的定義，圖是由頂點和邊組成的，分別考慮如何存儲頂點、如何存儲邊。6.2 圖的存儲結(jié)構(gòu)鄰接矩陣（Adjacency Matrix）在圖的鄰接矩陣表示中有一個記錄各個頂點信息的頂點表（一維數(shù)組）還有一個表示各個頂點之間鄰接關(guān)系的鄰接矩陣設(shè)圖 G = (V, E) 是一個有 n 個頂點的圖，則 G 的鄰接矩陣定義如下 Aij= 1 若(vi, vj)E 或 E 0 反之6.2 圖的存儲結(jié)構(gòu)例，無向圖的鄰接矩陣V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0

11、1 1 0 0 arc=V1 V2 V3 V4V1V2V3V46.2 圖的存儲結(jié)構(gòu)例，有向圖的鄰接矩陣V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V46.2 圖的存儲結(jié)構(gòu)從鄰接矩陣中可以反映圖的許多特征無向圖(1) 對稱矩陣（可采用壓縮存儲）；(2) 每一行（或列）1的個數(shù)是該頂點的度；(3) 主對角線全為0（簡單圖）。有向圖(1) 每一行1的個數(shù)是該頂點的出度； (2) 每一列1的個數(shù)是該頂點的入度；(3) 主對角線全為0（簡單圖）；(4) 有向圖的鄰接矩陣不一定對稱。6.2 圖

12、的存儲結(jié)構(gòu)帶權(quán)圖的鄰接矩陣Aij 0 i=j 其它 wij 若(vi, vj)E 或 E 6.2 圖的存儲結(jié)構(gòu)用鄰接矩陣表示的圖的類的定義 class AdjMatrix / 非帶權(quán)圖 int n； / 頂點的個數(shù) int matrixMaxSize MaxSize； / 鄰接矩陣 public: AdjMatrix(int m) n=m； ; / AdjMatrix class AdjMatrix / 帶權(quán)圖 const int INFINITE=； int n； /頂點的個數(shù) float matrixMaxSizeMaxSize； / 鄰接矩陣 public: AdjMatrix(int

13、m) n=m； ; / AdjMatrix6.2 圖的存儲結(jié)構(gòu)class AdjGraph AdjMatrix *adj；DataType *elem； public:AdjGraph(int m) adj=new AdjMatrix(m)； elm=new DataSet(m)；void CreateGraph(); / 建立一個圖G的鄰接矩陣Matrixint LocateVex(v) ; / 確定圖G中頂點v在頂點中的位置 DataType GetVex(v); / 得到圖G中頂點v的值int FirstAdjVex(v); / 確定圖G中頂點v的第一個鄰接點 int NextAdjVe

14、x(v,w);/ 確定圖G中頂點v相對于w的下一個鄰接點 void DFSTraverse(int v)；/圖的深度優(yōu)先遍歷 void BFSTraverse(int v)；/圖的廣度優(yōu)先遍歷; / AdjGraph6.2 圖的存儲結(jié)構(gòu)鄰接矩陣的優(yōu)點容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。?、找頂點的鄰接點等等。鄰接矩陣的缺點n 個頂點需要 nn 個單元存儲邊；空間效率為O(n2)。 對稀疏圖而言尤其浪費空間。6.2 圖的存儲結(jié)構(gòu)鄰接表（Adjacency List）表示法無向圖的鄰接表為每個頂點建立一個單鏈表第 i 個單鏈表中的結(jié)點表示與頂點 vi 所關(guān)聯(lián)的所有邊注：鄰接

15、表不唯一，因各個邊結(jié)點的鏈入順序是任意的。6.2 圖的存儲結(jié)構(gòu)問題在無向圖的鄰接表中，如何求每個頂點的度？ 第 i 個鏈表中的邊結(jié)點個數(shù)是頂點 i 的度若頂點數(shù)為 n，邊數(shù)為 e 時，則在無向圖的鄰接表中共需多少個結(jié)點？ n 個頂點結(jié)點，2e 個邊結(jié)點 6.2 圖的存儲結(jié)構(gòu)有向圖的鄰接表和逆鄰接表在有向圖的鄰接表中，第 i 個單鏈表鏈接的弧都是頂點vi發(fā)出的，也稱做出邊表。在有向圖的逆鄰接表中，第 i 個單鏈表鏈接的弧都是進入頂點 vi 的，也稱做入邊表。v1v2v3v4V4V3V2V12301V4V3V2V13020鄰接表逆鄰接表01230123 用鄰接表或逆鄰接表表示有向圖時，只需 n 個

16、頂點結(jié)點，e 個弧結(jié)點。6.2 圖的存儲結(jié)構(gòu)data：結(jié)點的數(shù)據(jù)域，保存頂點的數(shù)據(jù)值。firstout：結(jié)點的指針域，指向與該頂點相關(guān)聯(lián)的第一條邊 （?。┑牡刂繁眍^結(jié)點datafirstoutadjvexlink邊/弧結(jié)點adjvex：該邊或弧所指向的頂點的序號link：指向下一條邊或弧的指針adjvexlinkdatafirstout6.2 圖的存儲結(jié)構(gòu)網(wǎng)（帶權(quán)圖）的鄰接表邊/弧結(jié)點adjvexcostlink6.2 圖的存儲結(jié)構(gòu)鄰接表表示的圖的類定義class EArcNode /邊(或弧)結(jié)點 int adjvex； / 該邊或弧所指向的頂點的序號EArcNode *link； / 指向

17、下一條邊或弧的指針 public:EArcNode(int adj) adjvex=adj; link=NULL; friend class LinkGraph; / EArcNodeclass VNode / 表頭結(jié)點 DataType data； / 頂點的信息 EArcNode *firstout；/ 指向與該頂點關(guān)聯(lián)的第一條邊(弧) public: VNode (DataType e) data=e ; f irstout=NULL; friend class LinkGraph; / VNode6.2 圖的存儲結(jié)構(gòu)class LinkGraph /鄰接表 int n； / 頂點的個數(shù)

18、 VNode gheadMaxSize； / 鄰接表 public: LinkGraph(int m) n=m； void CreateGraph( ) ； / 建立圖g int LocateVex(v) ； / 得到頂點v在圖中的序號 DataType GetVex(v) ； / 得到頂點v的值 int FirstAdjVex(v) ； / 得到頂點v的第一個鄰接頂點 int NextAdjVex(v, w); / 確定圖G中頂點v相對于w的下一個鄰接點 void DFSTraverse(int v)； / 圖的深度優(yōu)先遍歷 void BFSTraverse(int v)； / 圖的廣度優(yōu)先

19、遍歷; / LinkGraph6.2 圖的存儲結(jié)構(gòu)圖的操作在鄰接表的上的實現(xiàn) int FirstAdjVex (int v) return gheadv-firstout.adjvex； / FirstAdjVex int NextAdjVex(int v，int w) p=gheadv-firstout； while (p & p-adjVex!=w) p=p-link； if (!p | !p-link) return 0； else return p-link-adjVex； / NextAdjVex6.2 圖的存儲結(jié)構(gòu)討論：鄰接表與鄰接矩陣的比較聯(lián)系都可以用來存儲有向圖和無向圖；鄰接表

20、中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。6.2 圖的存儲結(jié)構(gòu)區(qū)別對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。鄰接矩陣的空間復(fù)雜度為O(n2)，而鄰接表的空間復(fù)雜度為O(n+e)。鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2）；而鄰接表多用于稀疏圖的存儲（en2）。6.3 圖的遍歷圖的遍歷從圖中某一頂點出發(fā)，按照某種搜索路徑訪問圖中所有的頂點，使得每個頂點被訪問一次且僅被訪問一次。圖的遍歷操作要解決的關(guān)鍵問題在圖中，如何選取遍歷的起始頂點？ 解決方案：從編號小的頂點開始 6.3 圖的遍歷從某個起

21、點開始可能到達不了所有其它頂點，怎么辦？ 解決方案：多次調(diào)用從某頂點出發(fā)遍歷圖的算法。圖中可能存在回路，某些頂點可能會被重復(fù)訪問，如何避免遍歷因回路而陷入死循環(huán)。 解決方案：附設(shè)訪問標(biāo)志數(shù)組visitedn 在圖中，一個頂點可以和其它多個頂點相連，當(dāng)這樣的頂點訪問后，如何選取下一個要訪問的頂點？ 解決方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷6.3 圖的遍歷深度優(yōu)先遍歷DFS（Depth First Search）DFS算法思想從圖中某個頂點V0 出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至V0 的所有鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾

22、被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。6.3 圖的遍歷例深度優(yōu)先搜索過程 深度優(yōu)先生成樹6.3 圖的遍歷從訪問圖中某一起始點 v 開始，由 v 出發(fā)，訪問它的第一鄰接點 w1；再從 w1 出發(fā)，訪問與 w1鄰接但還沒有訪問過的頂點 w2；然后再從 w2 出發(fā)，進行類似的訪問， 如此進行下去，直到某一頂點所有的鄰接點都被訪問完。退回到上一步剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。6.3 圖的遍歷連通圖的深度優(yōu)先遍

23、歷算法void DFSTraverse( ) /深度優(yōu)先求圖的連通分量 int visitedn； /設(shè)置訪問標(biāo)志數(shù)組 for (v=0; vn; v+) visitedv=0； /初始化訪問標(biāo)志數(shù)組 for (v=0; vn; v+) if (!visitedv) DFS (v)；/每次從尚未訪問過的頂點出發(fā)/ DFSTraversevoid DFS (int v) /從頂點v出發(fā)訪問包含該頂點的最大連通子圖中的所有頂點 visitedv=1； visit(v)； for (w=firstAdjVex(v); w; w=nextAdjVex(v, w) if (!visitedw) DFS(

24、w)； / DFS6.3 圖的遍歷例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。V1V3V2V4V5V6V7V8深一層遞歸遞歸返回 V1遍歷序列：V1V2 V2V4 V4V5 V56.3 圖的遍歷例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。V1V3V2V4V5V6V7V8深一層遞歸遞歸返回 V1遍歷序列：V1V2 V2V4 V4V5V8 V86.3 圖的遍歷例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。V1V3V2V4V5V6V7V8深一層遞歸遞歸返回 V1遍歷序列：V1V2 V2V4 V4V5V86.3 圖的遍歷例，深度優(yōu)先遍歷序列，入棧序列，出棧序列。V1V3V2V4V5V6V7V8深一層遞歸遞歸返

25、回 V1遍歷序列：V1 V7V2V4V5V8V3 V3V6 V6V76.3 圖的遍歷不同存儲結(jié)構(gòu)下的DFS實現(xiàn)圖以鄰接矩陣存儲 void DFS (int v) visitedv=1; visit(v); for (w=0; w0) if (!visitedw) DFS(w); / DFS圖以鄰接表存儲void DFS(int v) visitedv=1; p=gheadv-firstout; while (p) w=p-adjvex; if (!visitedw ) DFS(w); p=p-link; / DFS6.3 圖的遍歷例V1V2V4V5V3V7V6V8例01231342datafi

26、rstout 1 6 7 2adjvexlink45 5 3 716785676深度遍歷：V1V3 V7 V6 V2 V4 V8 V56.3 圖的遍歷算法分析圖中有 n 個頂點，e 條邊。如果用鄰接矩陣存儲圖，則查找每一個頂點的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為O(n2)。如果用鄰接表存儲圖，在每一個單鏈 表中可以找到某個頂點 v 的所有鄰接頂點 w。由于總共有 2e 個邊結(jié)點(無向圖)，所以掃描邊的時間為O(e)。而且對所有頂點遞歸訪問1次，所以遍歷圖的時間復(fù)雜性為O(n+e)。6.3 圖的遍歷廣度優(yōu)先遍歷BFS（Breadth First Search）思路在訪

27、問了起始頂點 v 之后，由 v 出發(fā)，依次訪問 v 的所有未被訪問過的鄰接點 w1, w2, , wt，然后再順序訪問 w1, w2, , wt 的所有未被訪問過的鄰接點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有未被訪問過的鄰接點， ，如此重復(fù)，直到圖中所有頂點都被訪問完為止。6.3 圖的遍歷例 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹6.3 圖的遍歷說明廣度優(yōu)先遍歷是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先遍歷不是一個遞歸的過程，其算法也不是遞歸的。為了實現(xiàn)逐層訪問，算法中使用了一個隊列，以記憶正在訪問的頂點，以便向下一層訪問。與深度優(yōu)先

28、遍歷過程一樣，為避免重復(fù)訪問，需要一個輔助數(shù)組 visited n，對被訪問過的頂點加以標(biāo)記。6.3 圖的遍歷算法思想1）清隊列Q；2）對出發(fā)頂點 v 做v 入隊；標(biāo)記 v；3）當(dāng) Q 不空反復(fù)做：出隊頭元素到 u；訪問 u；將 u 的每個未被訪問的鄰接點 w 入隊；標(biāo)記 w。6.3 圖的遍歷廣度優(yōu)先搜索算法void BFS (int v) /廣度優(yōu)先求圖的連通分量 Q=new Queue( )； /清隊列Q Q.Enter(v)； /每次從尚未訪問過的頂點中選取一個頂點v visitedv=1； /標(biāo)記v while (!Q.Empty() /Q不空 u=Q.Leave()； /出隊頭元素到

29、u visited(u)； /訪問u for (w=FirstAdjVex(u); w; w=NextAdjVex(u, w) if (!visitedw) Q.Enter(w)； /將u的每個未被訪問的鄰接點w 入隊 visitedw=1； / BFS6.3 圖的遍歷BFS從出發(fā)點只能遍歷一個連通分量，若對任意圖的遍歷需要對每個分量中一個未被訪問的頂點為出發(fā)點進行BFS遍歷。 void BFSTraverse() /廣度優(yōu)先求圖的連通分量 int visitedn； /設(shè)置訪問標(biāo)志數(shù)組 for (v=0；vn；v+) visitedv=0； /初始化訪問標(biāo)志 for (v=0；vn；v+)

30、if (!visitedv) BFS( v)； / BFSTraverse6.3 圖的遍歷例，廣度優(yōu)先遍歷序列，入隊序列，出隊序列。V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V8V4V1V2V36.3 圖的遍歷算法分析如果用鄰接矩陣存儲圖，則對于每一個被訪問過的頂點，循環(huán)要檢測矩陣中的 n 個元素，總的時間代價為O(n2)。如果用鄰接表存儲圖，則循環(huán)的總時間代價為 D0 + D1 + + Dn-1 = O(e)，其中的 Di 是頂點 i 的度。而且對所有頂點訪問1次，所以遍歷圖的時間復(fù)雜性為O(n+e)。6.3 圖的遍歷DFS 與 BFS 之比較空間

31、復(fù)雜度相同，都是O(n)（借用了堆?；蜿犃校?；時間復(fù)雜度只與存儲結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無關(guān)。6.4 無向圖的應(yīng)用最小生成樹生成樹包含連通無向圖中全部頂點的極小連通子圖（n 個頂點、n-1 條邊）一個連通圖的生成樹不唯一使用不同的遍歷圖的方法，可以得到不同的生成樹從不同的頂點出發(fā)，也可能得到不同的生成樹對于非連通圖，通過圖的遍歷，得到的是生成森林6.4 無向圖的應(yīng)用最小生成樹例（a）深度優(yōu)先生成樹 （b） 廣度優(yōu)先生成樹V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V86.4 無向圖的應(yīng)用最小生成樹最小生成樹MST（Minimum-cost Spanning T

32、ree）連通無向網(wǎng)中邊權(quán)之和最小的生成樹最小生成樹MST的典型用途假設(shè)在 7 個城市之間要建立通信網(wǎng)絡(luò)線，要求使得每個城市之間連通且費用最少。數(shù)學(xué)模型連通網(wǎng)表示7個城市間的通信網(wǎng)頂點表示城市邊表示城市間的通信線路邊的權(quán)值表示線路的經(jīng)濟代價28123456710161418122524226.4 無向圖的應(yīng)用最小生成樹構(gòu)造最小生成樹的準(zhǔn)則必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；必須使用且僅使用 n-1 條邊來連接網(wǎng)絡(luò)中的 n 個頂點；不能使用產(chǎn)生回路的邊。求一個連通無向網(wǎng)中最小生成樹的方法Prim 算法Kruskal 算法都是利用MST的性質(zhì)構(gòu)造最小生成樹6.4 無向圖的應(yīng)用最小生成樹最小生成樹

33、的性質(zhì)若集合 U 是集合 V 的一個非空子集，若 (u, v) 是一條具有最小權(quán)值的邊，其中 uU，vV-U；則：(u, v) 必在最小生成樹上。UV-U6.4 無向圖的應(yīng)用最小生成樹Prim 算法Prim 算法的基本思想設(shè)連通 N= V, E ，T 是 N 的最小生成樹中邊的集合， U 是生成樹的頂點集合。（1） T= ，U= u （ u 為任一頂點）； （2）在所有 uU，vV-U 的邊 (u, v)E 中找一條代價最小的邊 (u, v) 加入集合 T 中，同時 v 加入 U； （3）重復(fù)（2），直到 U=V 為止。6.4 無向圖的應(yīng)用最小生成樹例012634528161222251025

34、1418T = U = 0 Min10, 28=10(0,5), 5Min25, 28=25, (5,4), 4Min28, 25, 22=22, (4,3), 3Min28, 25, 18, 12=12, (3,2), 2Min28, 25, 18, 16=16, (2,1), 1Min25, 18, 14=14, (1,6), 6 U=V，算法結(jié)束6.4 無向圖的應(yīng)用最小生成樹Prim 算法的實現(xiàn)圖的存儲：鄰接矩陣在構(gòu)造過程中，還設(shè)置了一個輔助數(shù)組closedge：每個元素closedgev有兩個域 lowcost：存放生成樹頂點集合內(nèi)頂點到生成樹外各頂點v的各邊上的當(dāng)前最小權(quán)值adjve

35、x：記錄生成樹頂點集合外各頂點距離集合內(nèi)哪個頂點最近（即權(quán)值最?。?.4 無向圖的應(yīng)用最小生成樹從頂點0出發(fā)利用Prim算法構(gòu)造最小生成樹過程中輔助數(shù)組各分量的值的變化i1 23456closedgeadjvexlowcost0280000100525422424312318216i1 23456edgeadjvexlowcost1140123456U10000005250101142213121216111416.4 無向圖的應(yīng)用最小生成樹利用 Prim 算法求最小生成樹的算法class AddArray int adjvex; float lowcost;/ AddArrayvoid Mi

36、nSpanTree_Prim (int u, AddArray closedge, AddArray edge, AdjMatrix G)/ 設(shè)圖以鄰接矩陣存儲，用Prim算法從頂點u出發(fā)構(gòu)造網(wǎng)G的最小生成樹且保存到數(shù)組edge中 for(v=0；vn；v+) Uv=0； Uu=1； for (v=0；v n；v+) if（u!=v) closedgev.adjvex=u;6.4 無向圖的應(yīng)用最小生成樹 closedgev.lowcost=G.matrixuv; for (t=1；tn；t+) /選擇其余的n-1個頂點 k=minimum(closedge)； /求出T的下一個頂點k頂點 u=

37、closedgek.adjvex； edgek.lowcost=G.matrixku; /保存選中邊的權(quán)值 edgek.adjvex=u; /保存選中邊的頂點 Uk=1； for (j=0；jG.matrixkj) closedgej.lowcost=G.matrixkj； closedgej.adjvex=k； / for / MinSpanTree_Prim6.4 無向圖的應(yīng)用最小生成樹Prime 算法分析設(shè)連通無向網(wǎng)有 n 個頂點，則該算法的時間復(fù)雜度為O(n2)適用于稠密的網(wǎng)絡(luò)6.4 無向圖的應(yīng)用最小生成樹Kruscal 算法基本思想 先構(gòu)造一個只含 n 個頂點、不含有邊的零圖 T ，

38、然后從權(quán)值最小的邊開始，若它的添加不使 T 產(chǎn)生回路，則在 T 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止。6.4 無向圖的應(yīng)用最小生成樹例1012141625226.4 無向圖的應(yīng)用最小生成樹算法思想設(shè)無向連通圖 G=(V, E) 的最小生成樹為 T=(U, TE)1）初始化：U=V；TE= ；2）循環(huán)直到 T 中的連通分量個數(shù)為 1在 E 中尋找最短邊 (u, v)；如果頂點 u、v 位于 T 的兩個不同的連通分量，則將邊 (u, v) 并入 TE，并將這兩個連通分量合為一個；在 E 中標(biāo)記邊 (u, v)，使之不參加后續(xù)最短邊的選取。有向圖可以用來描述一個工程（或系統(tǒng)）的進行過程

39、。每個工程由若干個子工程（活動）組成，完成了這些子工程整個工程就結(jié)束了。這些子工程間有兩種關(guān)系有先后順序：即前一子工程結(jié)束后一子工程才能開始無先后順序：即兩個子工程誰先誰后都互不影響 6.5 有向圖的應(yīng)用6.5 有向圖的應(yīng)用例，學(xué)生的學(xué)習(xí)就是一個工程，每一門課程的學(xué)習(xí)就是整個工程的一些活動。其中有些課程要求有先修課程，有些則不要求。C1高等數(shù)學(xué)C2計算機基礎(chǔ)C3離散數(shù)學(xué)C1, C2 C4數(shù)據(jù)結(jié)構(gòu)C3, C2C5高級語言程序設(shè)計C2C6編譯原理C5, C4C7操作系統(tǒng)C4, C9C8普通物理C1C9計算機原理C8 課程代號課程名稱先修課程6.5 有向圖的應(yīng)用兩個問題整個工程能否順利進行？哪些活動

40、是影響工程按期完工的關(guān)鍵？ 拓?fù)渑判?關(guān)鍵路徑6.5 有向圖的應(yīng)用拓?fù)渑判駻OV 網(wǎng)用頂點表示活動，用弧表示活動間的優(yōu)先關(guān)系的有向圖，稱為頂點表示活動的網(wǎng)（Activity On Vertices）若是圖中的有向邊，則表示活動 vi 必須先于活動 vj 進行AOV 網(wǎng)中不允許有回路，這意味著某項活動不能以自己為先決條件6.5 有向圖的應(yīng)用拓?fù)渑判蚶龑W(xué)生課程學(xué)習(xí)工程圖6.5 有向圖的應(yīng)用拓?fù)渑判蛴山o定的 AOV 網(wǎng)所描述的工程是否可行？檢測方法：拓?fù)渑判驅(qū)τ邢驁D構(gòu)造其頂點的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點都在它的拓?fù)溆行蛐蛄兄校瑒t該 AOV 網(wǎng)必定不存在回路，工程可行。相反，如果得不到滿足要求的拓?fù)?/p>

41、有序序列，則說明AOV 網(wǎng)中存在有向回路，此 AOV 網(wǎng)所代表的工程是不可行的。6.5 有向圖的應(yīng)用拓?fù)渑判蚋拍钔負(fù)洌ㄓ行颍┬蛄性?AOV 網(wǎng)中若將各個頂點（代表各個活動）排列成一個線性有序的序列 v1, v2, , vn，使得若從頂點 vi 到 vj 有一條有向路徑，則在序列中頂點 vi 必須排在頂點 vj 之前。拓?fù)渑判蛟?AOV 網(wǎng)中找一個拓?fù)湫蛄械倪^程。6.5 有向圖的應(yīng)用拓?fù)渑判蚶?，對學(xué)生選課工程圖進行拓?fù)渑判颍玫降耐負(fù)溆行蛐蛄袨?C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4

42、 , C7 , C6拓?fù)湫蛄胁⒉晃ㄒ?.5 有向圖的應(yīng)用拓?fù)渑判蚶?，對下列有向圖不能求得它的拓?fù)溆行蛐蛄蠦DAC因為圖中存在一個有向回路 B, C, D6.5 有向圖的應(yīng)用拓?fù)渑判蛲負(fù)渑判虻乃枷胼斎胍粋€ AOV 網(wǎng)，令 n 為頂點個數(shù)。(1) 在 AOV 網(wǎng)中選一個沒有前驅(qū)的頂點，并輸出之。(2) 從圖中刪去該頂點，同時刪去與該頂點關(guān)聯(lián)的弧。(3) 重復(fù)以上 (1)、(2) 步，直到全部頂點均已輸出，拓?fù)湫蛄行纬?，拓?fù)渑判蛲瓿?；或圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點了。這時 AOV 網(wǎng)中一定存在有向回路。6.5 有向圖的應(yīng)

43、用拓?fù)渑判蚶齟abcghdfabhcdgfe在算法中需要用定量的描述替代定性的概念 入度為零的頂點 弧頭頂點的入度減 1輸出沒有前驅(qū)的頂點刪除頂點及以它為尾的弧6.5 有向圖的應(yīng)用拓?fù)渑判蛲負(fù)渑判虻乃惴ㄋ枷雸D的存儲：鄰接表增設(shè)一個數(shù)組 indegree ，記錄各個頂點的入度在輸入數(shù)據(jù)時，每輸入一條弧，就需要建立一個弧結(jié)點，將它鏈入相應(yīng)弧鏈表中，并統(tǒng)計入度信息 EArcNode *p = new EArcNode (k); plink = gheadj.firstout; gheadj.firstout = p; indegreek+;/頂點 k 入度加1 6.5 有向圖的應(yīng)用拓?fù)渑判蚴褂靡粋€鏈

44、式棧，存放入度為零的頂點只要出現(xiàn)入度為零的頂點，就將它加入棧中由于表頭結(jié)點的“入度計數(shù)域”在變成0之后，已經(jīng)無用，故用它作為鏈?zhǔn)綏Ｊ褂庙旤c棧的拓?fù)渑判蛩惴梢悦枋鋈缦?1) 建立入度為零的頂點棧；(2) 當(dāng)入度為零的頂點棧不空時，重復(fù)執(zhí)行 從頂點棧中退出一個頂點，并輸出之；該頂點發(fā)出的所有弧的終點的入度減1；如果弧的終點入度減為至0，則該頂點壓入頂點棧；(3) 如果輸出頂點個數(shù)少于 AOV 網(wǎng)的頂點個數(shù)，則說明網(wǎng)中存在有向回路；否則拓?fù)渑判蛲瓿伞?.5 有向圖的應(yīng)用拓?fù)渑判蛲負(fù)渑判虻乃惴╞ool TopologicalSort () FindInDegree (indegree)； top=-

45、1; for (i=0；i-1) i=top; top=indegreetop; coutlink) k=p-adjvex； if (!(-indegreek) indegreek=top； top=k; /for /while if (countn) return false； return true； /TopologicalSort6.5 有向圖的應(yīng)用拓?fù)渑判蚶?.5 有向圖的應(yīng)用拓?fù)渑判蛲負(fù)渑判虻乃惴ǚ治鲈O(shè)AOV網(wǎng)中有 n 個頂點，e 條弧在拓?fù)渑判虻倪^程中，建立頂點棧所需要的時間是O(n)一般情況下，每個頂點進一次棧，出一次棧，共輸出 n 次頂點入度減 1 的運算共執(zhí)行了 e 次總的

46、時間復(fù)雜度為 O(n+e)6.5 有向圖的應(yīng)用關(guān)健路徑AOE網(wǎng)在沒有回路的有向網(wǎng)中，如果用頂點表示事件（Event） 用弧表示一個工程中的各項活動（Activity）用弧上的權(quán)值表示活動的持續(xù)時間（Duration）則稱這樣的有向圖為用弧表示活動的網(wǎng)（Activity on Edge）6.5 有向圖的應(yīng)用關(guān)健路徑例在 AOE 網(wǎng)中，有些活動（?。╉樞蜻M行，有些活動并行進行。從始點到終點的有向路徑可能不止一條，完成不同路徑的活動所需的時間也可能不同，但只有各條路徑上所有活動都完成了，整個工程才算完成。6.5 有向圖的應(yīng)用關(guān)健路徑AOE 網(wǎng)在某些工程預(yù)算方面非常有用，它可以使人們了解到完成整個工程

47、最短需要多少時間（假設(shè)網(wǎng)中沒有有向回路）？為縮短完成工程所需的時間，應(yīng)當(dāng)加快哪些活動？6.5 有向圖的應(yīng)用關(guān)健路徑問題1完成工程的最短時間？完成整個工程所需的最短時間定義為從開始頂點到結(jié)束頂點的最長路徑的長度，即在這條路徑上所有活動的持續(xù)時間之和最大。從開始頂點到結(jié)束頂點的這條最長的路徑稱為關(guān)鍵路徑（Critical Path）關(guān)鍵路徑上的所有活動稱為關(guān)鍵活動說明：關(guān)鍵路徑可能不止一條6.5 有向圖的應(yīng)用關(guān)健路徑問題2為縮短工期，應(yīng)當(dāng)加快哪些活動？要找出關(guān)鍵路徑，必須找出關(guān)鍵活動，只有提高關(guān)鍵活動的功效，才可能縮短整個工期。關(guān)鍵路徑為： (v0, v1, v4, v6, v8 ) 或 (v0,

48、 v1, v4, v7, v8 )關(guān)鍵路徑的長度為：18關(guān)鍵活動為：a1, a4, a7, a10, a8, a116.5 有向圖的應(yīng)用關(guān)健路徑定義幾個與計算關(guān)鍵活動有關(guān)的量e(i)活動 ai 的最早開始時間l(i) 活動 ai 的最遲開始時間活動 ai 用弧 表示dut() 表示活動 ai 持續(xù)的時間關(guān)鍵活動：e(i)=l(i) 的活動 ai 6.5 有向圖的應(yīng)用關(guān)健路徑ee(i)事件 vi 的最早發(fā)生時間從始點 v0 到頂點 vi 的最長路徑長度le(i)事件 vi 的最晚發(fā)生時間在保證終點 vn-1 在 le(n-1) 時刻完成的前提下，事件 vi 的最晚發(fā)生時間P(j) 表示以頂點 v

49、j 為弧頭的所有弧的尾頂點集合S(j) 表示以頂點 vj 為弧尾的所有弧的頭頂點集合6.5 有向圖的應(yīng)用關(guān)健路徑例ee(1)=6ee(2)=4le(4)=7a4= a5=e(4)=ee(1)=6e(5)=ee(2)=4l(4)=le(4)-dut()=6l(5)=le(4)-dut()=6是關(guān)鍵活動， 不是關(guān)鍵活動6.5 有向圖的應(yīng)用關(guān)健路徑求關(guān)鍵路徑的算法思想1）建立AOE網(wǎng)；2）從始點 v0 出發(fā)，令 ee(0)=0，邊進行拓?fù)渑判颍呌嬎闫溆喔黜旤c的 ee(i)。若圖中有回路則結(jié)束。3）從終點 vn-1 出發(fā)，le(n-1)=ee(n-1)，按逆拓?fù)溆行虻捻樞蚯?le(i)，i=n-2,

50、 , 0。4）根據(jù)各點的 ee 和 le 的值，求每個活動（弧）的最早開始時間 e(i) 和最遲開始時間 l(i)。若某弧滿足條件 e(i) = l(i)，則對應(yīng)活動是關(guān)鍵活動。6.5 有向圖的應(yīng)用關(guān)健路徑算法bool TopologicalSort(Stack &T) /求以鄰接表存儲的有向圖中各頂點事件的最早發(fā)生時間ee。/S是入度為零頂點棧，T為拓?fù)湫蛄许旤c棧。若該有向圖無回路，則該算法返回true且棧T返回該有向圖的一個拓?fù)湫蛄?，否則返回false。 Stack S; FindInGegree(indegree) /求各頂點的入度indegree count=0; ee0.n-1=0;

51、 /初始化 for (k=0; klink) /對頂點j的每個后繼頂點入度減1 k=p-adjvex; if (-indegreek=0) S.Push(k); /若入度為0，則入棧S if (eej+dut()eek) eek=eej+dut(); /對j的各后繼點k修改eek if(countlink) k=p-adjvex; if (lek-dut()lej) lej=lek-dut(); for (j=0; jlink) k=p-adjvex; tag=(eej=lek-dut()?*: ; coutjkdut()eejlek-dut()tag; /CriticalPath6.5 有向

52、圖的應(yīng)用關(guān)健路徑例頂點eeileiv0v1v2v3v4v5v6v7v80645771614180668710161418活動eklkl-ea1a2a3a4a5a6a7a8a9a10a11000022033660462583770770710316160141406.5 有向圖的應(yīng)用關(guān)健路徑算法分析拓?fù)渑判蚯?eei 和逆拓?fù)溆行蚯?lei 時，所需時間為 O(n+e)求各個活動的 ek 和 lk 時所需時間為O(e)總共花費時間仍然是 O(n+e)6.6 最短路徑（Shortest Path）6.6 最短路徑（Shortest Path）求從某個源點到其余各點的最短路徑 Dijkstra 算法

53、每一對頂點之間的最短路徑 Floyd 算法6.6 最短路徑求單源最短路徑單源最短路徑問題如果從圖中某一頂點（稱為源點）到達另一頂點（稱為終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。問題解法Dijkstra 算法給定一個網(wǎng) G = V, E,W 與源點 v0，求從 v0 到 G中其它頂點的最短路徑。規(guī)定各邊（或?。┥系臋?quán)值大于或等于0。6.6 最短路徑求單源最短路徑Dijkstra 算法思想按路徑長度的遞增次序，逐步產(chǎn)生各條最短路徑。第一條最短路徑長度的求法這條路徑必定只含一條弧 ，并且這條弧的權(quán)值最小。w1w2wkwn-16.6 最短路徑求單源最短路徑第二

54、條最短路徑長度的求法 它只可能有兩種情況直接從源點到某頂點 v2 （只含一條?。脑袋c經(jīng)過頂點 v1，再到達該頂點 v2（由兩條弧組成）6.6 最短路徑求單源最短路徑其余最短路徑的求法或者是直接從源點到某頂點vk（只含一條?。┗蛘呤菑脑袋c經(jīng)過已求得最短路徑的頂點，再到達該頂點6.6 最短路徑求單源最短路徑例602010305010003421103421源點終點最短路徑路徑長度v0v110v2-v330v4100605090606.6 最短路徑求單源最短路徑Dijkstra 算法實現(xiàn)引入一個輔助數(shù)組dist它的每一個分量 disti 表示當(dāng)前找到的從源點 v0 到終點 vi 的最短路徑的長度初

55、始狀態(tài)若從源點 v0 到頂點 vi 有邊，則disti為該邊上的權(quán)值若從源點 v0 到頂點 vi 沒有邊，則disti為+ 每次求得一條最短路徑之后，其終點 vk 加入集合 S，然后對所有的 viV-S，修改其 disti 值6.6 最短路徑求單源最短路徑Dijkstra 算法描述如下初始化置S v0 ;disti cost0i, i= 1, ,n-1; / n為圖中頂點個數(shù)(1) 求出最短路徑的長度distk min disti , iV-S ; S S k ;(2) 修改對于每一個 iV-S， disti min disti, distk + costki ；(3) 重復(fù) (1) 和 (2

56、) n-1次。6.6 最短路徑求單源最短路徑計算最短路徑的圖鄰接矩陣類的定義const int Vexnum =20； /圖中最大頂點個數(shù)#define max /定義無窮大 class Graph /圖的類定義 float costVernumVernum； float dist Vexnum； /最短路徑長度數(shù)組 int pathVexnum； /最短路徑頂點序列數(shù)組 int findVexnum； /最短路徑頂點集public: void ShortestPath (int，int)； int choose ( int )；/ Graph6.6 最短路徑求單源最短路徑Dijkstra 描述的單源最短路徑算法void ShortestPath_DIJ (int v0; int path; int *dist) for (v=0; vVexnum; v+) findv=0; pathv=0; distv=costv0v; findv0=1; for (i=1; i Vexnum; i+) k=mini