數(shù)據(jù)結(jié)構(gòu) 第7章圖

1、.,1,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,多對多 （m:n),.,2,哥尼斯堡七橋問題 德國古城哥尼斯堡普雷格爾河七 橋問題：從任一橋頭出發(fā)，依次走過每座 橋，每座橋只走一次，最后回到出發(fā)點。 一筆畫問題,.,3,.,4,.,5,7.1 基本術語 7.2 存儲結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的連通性 7.5 圖的應用,第7章 圖,.,6,7.1 圖的基本術語,其中：V 是G 的頂點集合，是有窮非空集； E 是G 的邊集合，是有窮集。,問：當E(G)為空時，圖G存在否？ 答：還存在！但此時圖G只有頂點而沒有邊。,有向圖： 無向圖： 完全圖：,圖G中的每條邊都是有方向的； 圖G中的每條邊都是無方向的； 圖G任

2、意兩個頂點都有一條邊相連接；,若 n 個頂點的無向圖有 n(n-1)/2 條邊, 稱為無向完全圖 若 n 個頂點的有向圖有n(n-1) 條邊, 稱為有向完全圖,V=vertex E=edge,圖：記為 G( V, E ),有向邊(u, v)稱為弧，邊的始點u 叫弧尾，終點v 叫弧頭。,.,7,例：判斷下列4種圖形各屬什么類型？,無向,無向圖(樹),有向圖,有向,n(n-1)/2 條邊,n(n-1) 條邊,G1的頂點集合為V(G1)=0,1,2,3 邊集合為E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),完全圖,完全圖,.,8,證明：,證明：若是完全有向圖，則

3、n個頂點中的每個頂點都有一條弧指向其它n-1個頂點, 因此總邊數(shù)=n(n-1),證明：從可以直接推論出無向完全圖的邊數(shù)因為無方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為n(n-1)/2。, 完全無向圖有n(n-1)/2 條邊。, 完全有向圖有n(n-1)條邊。,.,9,稀疏圖：稠密圖：,設有兩個圖 G(V, E) 和 G(V, E)。若 V V 且 E E, 則稱 圖G 是 圖G 的子圖。,子 圖：,邊較少的圖。通常邊數(shù)遠少于nlogn 邊很多的圖。,無向圖中，邊數(shù)接近n(n-1)/2 有向圖中，邊數(shù)接近n(n-1),.,10,帶權圖：,即邊上帶權的圖。其中權是指每條邊可以標上具有某種含義的數(shù)

4、值（即與邊相關的數(shù)）。,連通圖：,在無向圖中, 若從頂點v1到頂點v2有路徑, 則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的, 則稱此圖是連通圖。 非連通圖的極大連通子圖叫做連通分量。,帶權圖,在有向圖中, 若對于每一對頂點vi和vj, 都存在一條從vi到vj和從vj到vi的路徑, 則稱此圖是強連通圖。,強連通圖：,網(wǎng) ：,非強連通圖的極大強連通子圖叫做強連通分量。,.,11,生成樹：,是一個極小連通子圖，它含有圖中全部n個頂點，但只有n-1條邊。,若干棵生成樹的集合，含全部頂點，但構(gòu)成這些樹的邊或弧是最少的。,有兩類圖形不在本章討論之列：,圖的基本術語(續(xù)),如果在生成樹上添加

5、1條邊，必定構(gòu)成一個環(huán)。 若圖中有n個頂點，卻少于n-1條邊，必為非連通圖。,生成 森林：,.,12,鄰接點：,有向邊(u, v)稱為弧，邊的始點u 叫弧尾，終點v 叫弧頭。,頂點 v 的入度是以 v 為終點的有向邊的條數(shù), 記作 ID(v); 頂點 v 的出度是以 v 為始點的有向邊的條數(shù), 記作 OD(v)。,若 (u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接頂點。,弧頭和弧尾：,入度和出度：,問：當有向圖中僅1個頂點的入度為0,其余頂點的入度均為1，此時是何形狀？,度：,頂點v 的度是與它相關聯(lián)的邊的條數(shù)。記作TD(v)。 在有向圖中, 頂點的度等于該頂點的入度與出度

6、之和。,U 的入度=? U 的出度=?,答：是樹！而且是一棵有向樹！,.,13,簡單路徑：,路徑上各頂點 v1,v2,.,vm 均不互相重復。,回路：,若路徑上第一個頂點 v1 與最后一個頂點vm 重合，則稱這樣的路徑為回路或環(huán)。,路徑：,在圖 G(V, E) 中, 若從頂點 vi 出發(fā), 沿一些邊經(jīng)過一些頂點 vp1, vp2, , vpm，到達頂點vj。則稱頂點序列 ( vi vp1 vp2 . vpm vj ) 為從頂點vi 到頂點 vj 的路徑。它經(jīng)過的邊(vi, vp1)、(vp1, vp2)、.、(vpm, vj)應當是屬于E的邊。,路徑長度：,非帶權圖的路徑長度是指此路徑上邊的條

7、數(shù)； 帶權圖的路徑長度是指路徑上各邊的權之和。,圖的術語（續(xù)）,.,14,ADT Graph 數(shù)據(jù)對象V： 數(shù)據(jù)關系 R： 基本操作P： ADT Graph,圖的抽象數(shù)據(jù)類型,V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。,R=VR；VR=|v,wV 且 P(v,w), 表示從v到w的弧， 謂詞P(v,w)定義了弧的意義或信息,CreatGraph ( 初始條件：V是圖的頂點集，VR是圖中弧的集合。 操作結(jié)果：按V和VR的定義構(gòu)造圖G。,注意：V 的大小寫含義不同！,InsertVex ( 初始條件：圖G存在，v 和圖中頂點有相同特征。 操作結(jié)果：在圖G中添加新頂點。,（參見教材P156-25

8、7）,.,15,7.2 圖的存儲結(jié)構(gòu),圖的特點：,鏈式存儲結(jié)構(gòu)：,順序存儲結(jié)構(gòu)：,難！,（多個頂點，無序可言，無法僅以頂點坐標表達相互關系）,可用多重鏈表,鄰接矩陣(數(shù)組)表示法 鄰接表(鏈式)表示法 十字鏈表表示法 鄰接多重表表示法,但可用數(shù)組描述元素間關系。,非線性結(jié)構(gòu)（m :n）,鄰接矩陣,鄰接表 十字鏈表 鄰接多重表,各種表示法成立的原則：存入電腦后能惟一復原,.,16, 建立一個頂點表和一個鄰接矩陣。,1. 鄰接矩陣（數(shù)組）表示法,例1：,鄰接矩陣：,A.Edge =,（ v1 v2 v3 v4 v5 ）,v1 v2 v3 v4 v5,0 1 0 1 0 1 0 1 0 1 0 1

9、0 1 1 1 0 1 0 1 0 1 1 1 0,分析1：無向圖的鄰接矩陣是對稱的； 分析2：頂點i 的度第 i 行 (列) 中1 的個數(shù)； 特別：完全圖的鄰接矩陣中，對角元素為0，其余全1。,頂點表：,無向圖的鄰接矩陣如何表示？,記錄各個頂點信息,表示各個頂點之間關系, 設圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是一個二維數(shù)組 A.Edgenn，定義為：,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,.,17,例2 ：有向

10、圖的鄰接矩陣如何表示？,分析1：有向圖的鄰接矩陣可能是不對稱的。 分析2：頂點vi的出度=第i行元素之和，OD(vi )= A.Edge i j 頂點vi的入度=第i列元素之和。ID(vi )= A.Edge j i 頂點的度=第i行元素之和+第i列元素之和, 即：TD( vi ) = OD( vi ) + ID( vi ),鄰接矩陣：,A.Edge =,( v1 v2 v3 v4 ),v1 v2 v3 v4,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,注：在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點vi為尾的弧(即出度邊）； 第i列含義：以結(jié)點vi為頭的弧(即入度邊）。,頂

11、點表：,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,.,18,容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。?、找頂點的鄰接點等等。 n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。,例3 ： 有權圖（即網(wǎng)絡）的鄰接矩陣如何表示？,定義：,以有向網(wǎng)為例：,鄰接矩陣：, ,N.Edge =,( v1 v2 v3 v4 v5 v6 ),鄰接矩陣法優(yōu)點：,鄰接矩陣法缺點：,頂點表：,5 7 4 8 9 5 6 5 3 1, 5 7 4 8 9 5 6 5 3 1 ,v1 v2 v3 v4 v

12、5 v6,對稀疏圖而言尤其浪費空間。,.,19,注：用兩個數(shù)組分別存儲頂點表和鄰接矩陣 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /假設的最大頂點數(shù) Typedef enum DG, DN, AG, AN GraphKind; /有向/無向圖，有向/無向網(wǎng),圖的鄰接矩陣在機內(nèi)如何表示？ （參見教材P161）,對于n個頂點的圖或網(wǎng)，空間效率=O(n2),Typedef struct ArcCell /弧（邊）結(jié)點的定義 VRType adj; /頂點間關系，無權圖取1或0；有權圖取權值類型 InfoType *info; /該

13、弧相關信息的指針 ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;,Typedef struct /圖的定義 VertexType vexs MAX_VERTEX_NUM ; /頂點表，用一維向量即可(n) AdjMatrix arcs; /鄰接矩陣n*n Int Vernum, arcnum; /頂點總數(shù)n，?。ㄟ叄┛倲?shù)e GraphKind kind; /圖的種類標志 Mgraph;,.,20,Status CreateUDN(Mgraph /輸入n個頂點值，存入一維向量,例：用鄰接矩陣生成無向網(wǎng)的算法（參見教材P162）,對于n個頂點e

14、條弧的網(wǎng)， 建網(wǎng)時間效率 = O(n+n2+e*n),for(i=0; iG.vexnum; +i) /對鄰接矩陣n*n個單元初始化，adj=,info=NULL for(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL;,for(k=0;kG.arcnum;+k) /給鄰接矩陣有關單元賦初值(循環(huán)次數(shù)弧數(shù)e scanf( /如果弧有信息則填入 G.arcsij = G.arcs j i； /無向網(wǎng)是對稱矩陣 ,return OK; / CreateUDN,.,21,2. 鄰接表（鏈式）表示法, 對每個頂點vi 建立一個單鏈表，把與vi有關聯(lián)的邊的信息（即度或

15、出度邊）鏈接起來，表中每個結(jié)點都設為3個域:, 每個單鏈表還應當附設一個頭結(jié)點（設為2個域），存vi信息；,表結(jié)點,頭結(jié)點,鄰接點域，表示vi 鄰接點的位置,鏈域，指向下一個邊或弧的結(jié)點,數(shù)據(jù)域，與邊有關信息（如權值）,數(shù)據(jù)域，存儲頂點vi 信息,鏈域，指向單鏈表的第一個結(jié)點, 每個單鏈表的頭結(jié)點另外用順序存儲結(jié)構(gòu)存儲。,.,22,例1：無向圖的鄰接表如何表示？,鄰接表,例2：有向圖的鄰接表如何表示？,鄰接表(出邊),逆鄰接表(入邊),請注意：鄰接表不惟一！因各個邊結(jié)點的鏈入順序是任意的。,v1鄰接點v4的位置,此無權圖未開第3分量,.,23,例3：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡。,8

16、0,64,1,2,5,當鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！,.,24,分析1: 對于n個頂點e條邊的無向圖，鄰接表中除了n個頭結(jié)點外，只有2e個表結(jié)點,空間效率為O(n+2e)。 若是稀疏圖(en2)，則比鄰接矩陣表示法O(n2)省空間。,鄰接表存儲法的特點：,分析2:在有向圖中，鄰接表中除了n個頭結(jié)點外，只有e個表結(jié)點,空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。,它其實是對鄰接矩陣法的一種改進,怎樣計算無向圖頂點的度？,鄰接表的缺點：,怎樣計算有向圖頂點的出度？ 怎樣計算有向圖頂點的入度？ 怎樣計算有向圖頂點Vi的度：,需遍歷全表,鄰接表的優(yōu)點：,TD(Vi)=單鏈表中

17、鏈接的結(jié)點個數(shù),OD(Vi)單鏈出邊表中鏈接的結(jié)點數(shù) I D( Vi ) 鄰接點為Vi的弧個數(shù),TD(Vi) = OD( Vi ) + I D( Vi ),空間效率高；容易尋找頂點的鄰接點；,判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應的單鏈表，沒有鄰接矩陣方便。,.,25,討論：鄰接表與鄰接矩陣有什么異同之處？,1. 聯(lián)系：鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。 2. 區(qū)別： 對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關）。 鄰接矩陣的空間復雜度為O(n2),而鄰接表的空間復雜度為O(n+e)。

18、 3. 用途： 鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)； 而鄰接表多用于稀疏圖的存儲（en2),.,26,圖的鄰接表在機內(nèi)如何表示？ （參見教材P163）,#define MAX_VERTEX_NUM 20 /假設的最大頂點數(shù),空間效率為O(n+2e)或O(n+e) 時間效率為O(n+e*n),Typedef struct VNode /頂點結(jié)構(gòu) VertexType data; /頂點信息 ArcNode * firstarc; /指向依附該頂點的第一條弧的指針 VNode, AdjList MAX_VERTEX_NUM ;,Typedef struct /圖結(jié)構(gòu) AdjLis

19、t vertics ; /應包含鄰接表 int vexnum, arcnum; /應包含頂點總數(shù)和弧總數(shù) int kind; /還應說明圖的種類（用標志） ALGraph;,Typedef struct ArcNode /弧結(jié)構(gòu) int adjvex; /該弧所指向的頂點位置 struct ArcNode *nextarcs; /指向下一條弧的指針 InfoArc *info; /該弧相關信息的指針 ArcNode；,圖的鄰接表生成算法作為自測題,.,27,它是有向圖的另一種鏈式結(jié)構(gòu)。 思路：將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結(jié)合。 1、開設弧結(jié)點，設5個域（每段弧是一個數(shù)據(jù)元素） 2

20、、開設頂點結(jié)點，設3個域（每個頂點也是一個數(shù)據(jù)元素）,data : 頂點信息 Firstin : 以頂點為弧頭的第一條弧結(jié)點 Firstout: 以頂點為弧尾的第一條弧結(jié)點,頂點結(jié)點,弧結(jié)點,3. 十字鏈表表示法,tailvex: 弧尾頂點位置 headvex: 弧頭頂點位置 hlink: 弧頭相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息,n個頂點的集合怎樣儲存？,仍用順序存儲結(jié)構(gòu),.,28,例：畫出有向圖的十字鏈表。,十字鏈表優(yōu)點：容易操作，如求頂點的入度、出度等。,此無權圖未開第4分量,空間復雜度和建表的時間復雜度都與鄰接表相同。,.,29,#define MA

21、X_VERTEX_NUM 20,十字鏈表存儲結(jié)構(gòu)描述：,Typedef struct ArcBox /弧結(jié)點結(jié)構(gòu)，5分量 int tailvex , headvex ; struct ArcBox * hlink , tlink; InfoType *info; ArcBox;,Typedef struct VexNode /頂點結(jié)構(gòu), 3分量 VertexType data; ArcBox * firstin,*firstout; VexNode;,Typedef struct /圖結(jié)構(gòu),整體概念 VexNode xlist MAX_VERTEX_NUM ; /表頭向量 int vexnum

22、, arcnum; OLGraph;,.,30,這是無向圖的另一種存儲結(jié)構(gòu)，當對邊操作時建議采用此種結(jié)構(gòu)存儲。 1、設立邊結(jié)點， 6個域（每條邊是一個數(shù)據(jù)元素） 2、設立頂點結(jié)點， 2個域（每個頂點也是一個數(shù)據(jù)元素）,邊結(jié)點,data : 存儲頂點信息 Firstedge : 依附頂點的第一條邊結(jié)點,頂點結(jié)點,4. 鄰接多重表表示法,mark：標志域 ivex， jvex : 邊依附的兩個頂點位置 ilink: 指向下一條依附頂點 i 的邊位置 jlink; 指向下一條依附頂點 j 的邊位置 info: 邊信息,n個頂點的集合怎樣儲存？,仍用順序存儲結(jié)構(gòu),.,31,例：畫出無向圖的鄰接多重表,

23、鄰接多重表優(yōu)點： 容易操作，如求頂點的度等。,空間復雜度和建表的時間復雜度都與鄰接表相同。,此無權圖未開第6分量,.,32,一、深度優(yōu)先搜索 二、廣度優(yōu)先搜索,7.3 圖的遍歷,遍歷定義：從已給的連通圖中某一頂點出發(fā)，沿著一些邊，訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。,遍歷實質(zhì)：找每個頂點的鄰接點的過程。 圖的特點：圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。,解決思路：可設置一個輔助數(shù)組 visited n ，用來標記每個被訪問過的頂點。它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某

24、一個頂點i 被訪問，就立即改 visited i為1，防止它被多次訪問。,圖常用的遍歷：,怎樣避免重復訪問？,.,33,一、深度優(yōu)先搜索( DFS ),基本思想：仿樹的先序遍歷過程。,Depth_First Search,v1,DFS 結(jié)果,例1：,v2,v4,v8,v5,v3,v6,v7,例2：,v2 v1 v3 v5 ,DFS 結(jié)果,v4 v6,起點,起點,遍歷步驟,應退回到V8，因為V2已有標記,.,34,深度優(yōu)先搜索（遍歷）步驟：,詳細歸納： 在訪問圖中某一起始頂點 v 后，由 v 出發(fā)，訪問它的任一鄰接頂點 w1； 再從 w1 出發(fā)，訪問與 w1鄰接但還未被訪問過的頂點 w2； 然后

25、再從 w2 出發(fā)，進行類似的訪問， 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。 接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它未被訪問的鄰接頂點。 如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問； 如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。,簡單歸納： 訪問起始點 v; 若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點； 若當前鄰接點已訪問過，再找v的第2個鄰接點重新遍歷。,.,35,討論1：計算機如何實現(xiàn)DFS？,DFS 結(jié)果,鄰接矩陣 A,輔助數(shù)組 visited n ,起點,開輔助數(shù)組 visited n

26、 ！,例：,v2,v1,v3,v5,v4,v6,請注意逐級回退是遞歸概念,.,36,for( j=1; j=n; j+) if ( Av, j / DFS1,討論2： DFS算法如何編程？,DFS1(A, n, v) visit（v）; visitedv=1;,可以用遞歸算法！,/Ann為鄰接矩陣，v為起始頂點(編號）,/訪問（例如打?。╉旤cv,Av,j 1 有鄰接點,visited n =0 未訪問過,/訪問后立即修改輔助數(shù)組標志,/從v所在行從頭搜索鄰接點,（教材上DFS遞歸算法見P169）,.,37,討論3：在圖的鄰接表中如何進行DFS？,DFS 結(jié)果,輔助數(shù)組 visited n ,例

27、：,照樣借用visited n ！,起點,0 1 2 3,注意：在鄰接表中，并非每個鏈表元素（表結(jié)點）都被掃描到,因此遍歷速度很快。,v0,v1,v2,v3,.,38,討論4： 鄰接表的DFS算法如何編程？,（書上沒有，僅供參考）,/訪問后立即修改輔助數(shù)組標志,仍用遞歸算法,Int visited; /初始化輔助數(shù)組,元素均為0 Void DFS(List,v,p) /設p為v的頭指針 visit(v); /訪問起點 visitedv=1; /起點已訪問,0變1 while(p-link) /當存在起點的第一個鄰接點時 p=p-link; v=p-data; if(!visitedv)DFS(

28、List,v,p); /進行遞歸 return; ,.,39,DFS 算法效率分析:,（設圖中有 n 個頂點，e 條邊） 如果用鄰接矩陣來表示圖，遍歷圖中每一個頂點都要從頭掃描該頂點所在行，因此遍歷全部頂點所需的時間為O(n2)。 如果用鄰接表來表示圖，雖然有 2e 個表結(jié)點，但只需掃描 e 個結(jié)點即可完成遍歷，加上訪問 n個頭結(jié)點的時間，因此遍歷圖的時間復雜度為O(n+e)。,結(jié) 論： 稠密圖適于在鄰接矩陣上進行深度遍歷； 稀疏圖適于在鄰接表上進行深度遍歷。,.,40,二、廣度優(yōu)先搜索( BFS ),基本思想：仿樹的層次遍歷過程。,Breadth_First Search,v1,BFS 結(jié)果

29、,例1：,例2：,v3 ,BFS 結(jié)果,v4 v5 ,起點,遍歷步驟,起點,v2 v1 v6 ,v9 v8 v7,.,41,廣度優(yōu)先搜索（遍歷）步驟：,簡單歸納： 在訪問了起始點v之后，依次訪問 v的鄰接點； 然后再依次（順序）訪問這些點（下一層）中未被訪問過的鄰接點； 直到所有頂點都被訪問過為止。,廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有回退的情況。 因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。,.,42,討論1：計算機如何實現(xiàn)BFS？,鄰接表,寬度優(yōu)先搜索要借助隊列！,例：,起點,輔助隊列,v2已訪問過了,V2入隊,visited

30、 n 仍需要,BFS 遍歷結(jié)果,.,43,while(rear!=front) /隊不空時 front=(front+1)%n; v=qfront; /訪問過的頂點出隊 p=Listv.firstarc; /P指向第1個鄰接點 while(!p) if(! Visitedadjvex(p) )/未到表尾，且鄰接域未訪問過， Visit(adjvex(p); Visitedadjvex(p)=1;/則先輸出再改標記， rear=(rear+1)%n; qrear= adjvex(p) /最后再入隊 p=nextarc(p); /指向單鏈表中下一個鄰接點 return / BFS1,討論2： BF

31、S算法如何編程？,BFS1(List, n, v) /List為鄰接表，v為起點，Qn為輔助隊列 Visit(v); Visitedv=1; /訪問（例如打?。╉旤cv并修改標志,層次遍歷應當用隊列！,（教材上BFS算法見P170）,front=n-1;rear=0; /隊列指針初始化 qrear=v; /起始點入隊,.,44,BFS 算法效率分析:,DFS與BFS之比較： 空間復雜度相同，都是O(n)(借用堆棧或隊列裝n個頂點）； 時間復雜度只與存儲結(jié)構(gòu)（鄰接矩陣或鄰接表）有關，而與搜索路徑無關。,如果使用鄰接表來表示圖，則BFS循環(huán)的總時間代價為 d0 + d1 + + dn-1 = O(e

32、)，其中的 di 是頂點 i 的度。 如果使用鄰接矩陣，則BFS對于每一個被訪問到的頂點，都要循環(huán)檢測矩陣中的整整一行（ n 個元素），總的時間代價為O(n2)。,（設圖中有 n 個頂點，e 條邊）,.,45,7.4 圖的連通性問題,1. 求圖的生成樹 2. 求最小生成樹,.,46,1.求圖的生成樹（或生成森林）,生成樹：是一個極小連通子圖，它含有圖中全部頂點，但只有n-1條邊。 生成森林：由若干棵生成樹組成，含全部頂點，但構(gòu)成這些樹的邊是最少的。,思考1：若對連通圖進行遍歷，得到的是什么？ 得到的將是一個極小連通子圖，即圖的生成樹！ 由深度優(yōu)先搜索得到的生成樹，稱為深度優(yōu)先搜索生成樹。 由廣

33、度優(yōu)先搜索得到的生成樹，稱為廣度優(yōu)先搜索生成樹。 思考2：若對非連通圖進行遍歷，得到的是什么？ 得到的將是各連通分量的生成樹，即圖的生成森林！,.,47,例1 ：畫出下圖的生成樹,DFS生成樹,鄰接表,v0,v2,v1,v4,v3,BFS生成樹,v0,無向連通圖,.,48,其實由鄰接矩陣或鄰接表也能直接畫出生成森林,例2：畫出下圖的生成森林（或極小連通子圖）,求解步驟： Step1:先求出鄰接矩陣或鄰接表； Step2:寫出DFS或BFS結(jié)果序列； Step3:畫出對應子圖或生成森林。,這是一個無向非連通圖（參見教材P170-171例）,下面選用鄰接表方式來求深度優(yōu)先搜索生成森林,生成森林的定

34、義（對有向或無向圖均適用）：是若干棵生成樹的集合，含全部頂點，但構(gòu)成這些樹的邊或弧是最少的。,.,49,子圖1：,再寫出DFS結(jié)果ABMJLCF DE GHKI,先寫出鄰接表（或鄰接矩陣）：,子圖2：,子圖3：,最小連通！,怎樣找3個根？,.,50,子圖 (或連通分量),生成森林,.,51,2. 求最小生成樹,首先明確： 使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。 按照生成樹的定義，n 個頂點的連通網(wǎng)絡的生成樹肯定有 n 個頂點和僅僅n-1 條邊。,即有權圖,構(gòu)造最小生成樹的準則 必須只使用該網(wǎng)絡中的邊來構(gòu)造最小生成樹； 必須使用且僅使用n-1條邊

35、來聯(lián)結(jié)網(wǎng)絡中的n個頂點； 不能使用產(chǎn)生回路的邊。,目標：在網(wǎng)絡的多個生成樹中，尋找一個各邊權值之和最小的生成樹。,.,52,欲在n個城市間建立通信網(wǎng)，則n個城市應鋪n-1條線路；但因為每條線路都會有對應的經(jīng)濟成本，而n個城市可能有 n(n-1)/2 條線路，那么，如何選擇n1條線路使總費用最少？,典型用途：,先建立數(shù)學模型： 頂點表示城市，有n個； 邊表示線路，有n1條； 邊的權值表示線路的經(jīng)濟代價； 連通網(wǎng)表示n個城市間的通信網(wǎng)。,顯然此連通網(wǎng)是一棵生成樹！,問題抽象： n個頂點的生成樹很多，需要從中選一棵代價最小的生成樹，即該樹各邊的代價之和最小。此樹便稱為最小生成樹MST。,Minimu

36、m cost Spanning Tree,.,53,討論：如何求得最小生成樹？,最小生成樹（MST）的 性質(zhì)如下：,若U集是V的一個非空子集，若(u0, v0)是一條最小權值的邊，其中u0U，v0V-U；則：(u0, v0)必在最小生成樹上。,設想一下：先把權值最小的邊歸入生成樹內(nèi)，逐個遞增，舍去回路邊，則得到的很可能就是最小生成樹！,求MST有多種算法，但最常用的是以下兩種：,Kruskal（克魯斯卡爾）算法 Prim（普里姆）算法,Kruskal算法特點：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。 Prime算法特點: 將頂點歸并，與邊數(shù)無關，適于稠密網(wǎng)。,54,Kruskal算法示例：對邊操作

37、，歸并邊,Kruskal算法效率分析：,Kruskal算法的時間效率O（elog2e）,Kruskal算法是歸并邊，適用于稀疏圖（用鄰接表）,.,55,普利姆（Prim）算法示例： 歸并頂點,1,Prim算法效率分析：,Prim算法的時間效率O（n2）,Prim算法是歸并頂點，適用于稠密網(wǎng)。,.,56,圖5-4-5 構(gòu)造最小生成樹過程中輔助數(shù)組中各分量的值,圖5-4-5 構(gòu)造最小生成樹過程中輔助數(shù)組中各分量的值,.,57,7.5 有向無環(huán)圖及其應用,1. 拓撲排序 2. 求關鍵路徑,.,58,1 拓撲排序 在工程實踐中，一個工程項目往往由若干個子項目組成，這些子項目間往往有多種關系： 先后關系

38、，即必須在一子項目完成后，才能開始實施另一個子項目； 子項目之間無次序要求，即兩個子項目可以同時進行，互不影響。 在工廠中，一件設備的生產(chǎn)包括許多工序，各工序之間也存在這兩種關系。 學校里某個專業(yè)的課程學習，有些課程是基礎課，它們可以獨立于其它課程，即無前導課程；有些課程必須在一些課程學完后才能開始學。,.,59,這些類似的問題都可以用有向圖來表示，我們把這些子項目、工序、課程看成一個個頂點稱之為活動(Activity)。 如果從頂點Vi到Vj之間存在有向邊,則表示活動i必須先于活動j進行。這種圖稱做頂點表示活動的網(wǎng)絡(Activity On Vertex network,簡稱AOV網(wǎng)絡)。

39、例如表5-6-1是某校計算機專業(yè)的課程及其相互之間的關系，它對應的AOV網(wǎng)絡如圖5-6-1所示。,.,60,表5-6-1 某專業(yè)課程設置,.,61,圖5-6-1（a） AOV網(wǎng)絡,.,62,在AOV網(wǎng)絡中，如果頂點Vi的活動必須在頂點Vj的活動以前進行，則稱Vi為Vj的前趨頂點，而稱Vj為Vi的后繼頂點。這種前趨后繼關系有傳遞性。 AOV網(wǎng)絡中一定不能有有向環(huán)路。例如在圖5-6-1（b）那樣的有向環(huán)路中，V2是V3的前趨頂點，V1是V2的前趨頂點，V3又是V1的前趨頂點，環(huán)路表示頂點之間的先后關系進入了死循環(huán)。 因此，對給定的AOV網(wǎng)絡首先要判定網(wǎng)絡中是否存在環(huán)路，只有有向無環(huán)路網(wǎng)絡在應用中才

40、有實際意義。,.,63,圖5-6-1（b） 有向環(huán)路,.,64,所謂“拓撲排序”就是將AOV網(wǎng)絡中的各個頂點(各個活動)排列成一個線性有序序列，使得所有要求的前趨、后繼關系都能得到滿足。 由于AOV網(wǎng)絡中有些頂點之間沒有次序要求，它們在拓撲有序序列中的位置可以任意顛倒，所以拓撲排序的結(jié)果一般并不是唯一的。 通過拓撲排序還可以判斷出此AOV網(wǎng)絡是否包含有有向環(huán)路，若有向圖G所有頂點都在拓撲排序序列中，則AOV網(wǎng)絡必定不包含有有向環(huán)路。,.,65,拓撲排序方法,(1) 在AOV網(wǎng)中選擇一個沒有前驅(qū)（即入度為0）的頂點，并把它輸出； (2) 從網(wǎng)絡中刪去該頂點和從該頂點發(fā)出的所有有向邊； (3) 重

41、復執(zhí)行上述兩步，直到網(wǎng)中所有的頂點都被輸出 (此時，原AOV網(wǎng)絡中的所有頂點和邊就都被刪除掉了)。 如果進行到某一步，無法找到無前趨的頂點，則說明此AOV網(wǎng)絡中存在有向環(huán)路，遇到這種情況，拓撲排序就無法進行了。,.,66,C1,C10,C11,C6,C2,C12,C4,C8,C3,C7,C5,C9,拓撲有序序列： （C1，C2，C3，C4，C5，C7，C9，C10，C11，C6，C12，C8） （C9，C10，C11，C6，C1，C12，C4，C2，C3，C5，C7，C8）,.,67,0,1,0,1,0,2,1,1,.,68,圖5-6-2 AOV網(wǎng)及拓撲序列的產(chǎn)生過程,a b c d e f,

42、（a）AOV網(wǎng)；(b)輸出v0后；（c）輸出v5后；（d）輸出v3后；（e）輸出v2后；（f）輸出v1后。 這樣得到的一個拓撲排序序列為：v0, v5, v3, v2, v1, v4,.,69,為了實現(xiàn)拓撲排序，針對上述兩個步驟，采用鄰接表作為有向圖的存儲結(jié)構(gòu)，并且在表結(jié)點中增設一個入度，存放頂點的入度。例如圖5-6-2種的AOV網(wǎng)的鄰接表如圖5-6-3（a）所示。這樣，入度域為零的表結(jié)點及時無前驅(qū)的頂點，刪除該頂點及它為尾的弧的操作，則可以轉(zhuǎn)換為將它的所有弧頭頂點的入度減1來實現(xiàn),.,70,.,71,A,B,C,D,E,F,G,H,I,.,72,兩個事件之間只能畫一條箭線，表示一項作業(yè)。若兩

43、項或兩項以上作業(yè)同時開始或結(jié)束，就要引進虛事件和虛作業(yè)，虛作業(yè)不消耗資源。,.,73,3各項作業(yè)之間的關系及它們在網(wǎng)絡圖上的表達方式如下： 作業(yè)a結(jié)束后可以開始b和c，見圖(a)； 作業(yè)c在a和b均結(jié)束后才能開始，見圖(b)；,.,74,a、b兩項作業(yè)均結(jié)束后可以開始c和d，見圖(c)； 作業(yè)c在a結(jié)束后即可進行，但作業(yè)d必須同時在a和b結(jié)束后才能開始，見圖(d)。,.,75,表71,.,76,C,B,E,D,A,X2,X1,K,G,I,H,0,F,J,0,.,77,2.關鍵路徑,關鍵路徑法是采用邊表示活動(Activity On Edge)的網(wǎng)絡，簡稱為AOE網(wǎng)絡。 AOE網(wǎng)絡是一個帶權的有

44、向無環(huán)路圖，其中，每個頂點代表一個事件(Event)，事件說明某些活動或某一項活動的完成，即階段性的結(jié)果。 離開某頂點的各條邊所代表的活動，只有在該頂點對應的事件出現(xiàn)后才能開始。 權值表示活動持續(xù)的時間。,.,78,圖5-6-4 一個AOE網(wǎng)絡,.,79,AOE網(wǎng)絡,通常利用AOE網(wǎng)絡可以研究以下兩個問題： (1) 完成整個工程至少需要多少時間？ (2) 哪些活動是影響工程進度的關鍵？,.,80,關鍵路徑,完成工程所需的時間就是從開始點起進行到結(jié)束點止所需的時間。 路徑長度是指沿路徑各邊的權值之和，也就是這些邊所代表的活動所需時間之和。 完成整個工程所需的時間取決于從開始點到結(jié)束點的最長路徑長

45、度，此長度最大的路徑叫做關鍵路徑。 分析關鍵路徑的目的是辨別哪些是關鍵活動，以便爭取提高關鍵活動的效率，縮短整個工期。,.,81,在描述關鍵路徑的算法時，設活動ai由弧表示，要確定如下幾個相關的量： (1) 事件Vj的最早出現(xiàn)時間和活動的最早開始時間：從源點V1到某頂點Vj的最長路徑長度叫作事件j的最早出現(xiàn)時間，表示成Vej。頂點Vj的最早出現(xiàn)時間Vej決定了從Vj指出的各條邊所代表活動的最早開始時間，因為事件j不出現(xiàn)，它后面的各項活動就不能開始。我們以ei表示活動ai的最早開始時間。顯然ei= Vej 。 (2) 活動ai的最遲開始時間：在不影響整個工程按時完成的前提下，此項活動最遲的必須開

46、始時間，表示成Li。 只要某活動ai有Li=ei的關系，我們就稱ai為關鍵活動。關鍵活動只允許在一個確定的時間開始，再早，它前面的事件還沒出現(xiàn)，尚不能開始；再晚，又會延誤整個工程的按時完成。由于完成整個工程所需的時間是由關鍵路徑上各邊權值之和所決定的，顯然關鍵路徑上各條邊所對應的活動都是關鍵活動。,.,82,(3) 事件j的最遲出現(xiàn)時間：即事件j在不延誤整個工程的前提下允許發(fā)生的最遲時間，表示為VLj。對某條指向頂點Vj的邊所代表的活動ai可得到： Li= VLj-(活動ai所需時間) 也就是活動ai必須先于它后面事件的最遲出現(xiàn)時間開始，提前的時間為進行此活動所需的時間。 下圖所示為活動開始時

47、間與事件出現(xiàn)時間的關系。,確定關鍵路徑的方法就是要確定ei=Li的關鍵活動！,.,83,假設以wj,k表示有向邊的權，即此邊對應的活動所需的時間，為了求AOE網(wǎng)絡中活動ai的最早開始時間ei和活動ai的最遲開始時間Li，先要求得頂點Vk的事件Vk的最早出現(xiàn)時間Vek和最遲出現(xiàn)時間VLk 。,.,84,事件最早出現(xiàn)時間Ve（j）和最遲出現(xiàn)時間Vl（j）,Vek和VLk可以采用下面的遞推公式計算： (1) 向匯點遞推 由源點的Vv1=0開始，利用公式： 向匯點的方向遞推，可逐個求出各頂點的ev 。式中p表示所有指向頂點的邊的集合，如圖6.22所示。,.,85,圖7-6-6 集合p,此式的意義為：從

48、指向頂點Vk的各邊的活動中取最晚完成的一個活動的完成時間作為Vk的最早出現(xiàn)時間Vek。,.,86,(2) 向源點遞推 由上一步的遞推，最后總可求出匯點的最早出現(xiàn)時間evn。因匯點就是結(jié)束點，最遲出現(xiàn)時間與最早出現(xiàn)時間相同，即Lvn=evn。從匯點的最遲出現(xiàn)時間Lvn開始，利用下面公式： 向源點的方向往回遞推，可逐個求出各頂點的最遲出現(xiàn)時間Lv。式中s表示所有由Vj點指出的邊的集合，如圖6.23所示。,.,87,圖5-6-7 集合s,此公式的意義為：由從Vj頂點指出的各邊所代表的活動中取需最早開始的一個開始時間作為Vj的最遲出現(xiàn)時間。,.,88,無論是向匯點遞推還是向源點遞推，都必須按一定的頂點

49、順序進行。 對所有的有向邊，向匯點遞推是先求出尾頂點的ev值，再求頭頂點的ev值；向源點遞推則相反，先求頭頂點的Lv值，再求尾頂點的Lv值。 為此，可利用上節(jié)介紹的拓撲排序得到的頂點次序進行向匯點的遞推，向源點的遞推按相反的順序進行即可，不必再重新排序。,.,89,7.5.2 關鍵路徑算法,(1) 輸入e條有向邊，建立AOE網(wǎng)絡的存儲結(jié)構(gòu)； (2) 從源點出發(fā)，令ev1 =0，按拓撲排序的序列求其余各頂點的最早出現(xiàn)時間evi(2in)。若拓撲排序序列中的頂點個數(shù)小于網(wǎng)絡中的頂點數(shù)n，則說明網(wǎng)絡中存在環(huán)路，算法中止執(zhí)行；否則執(zhí)行(3)； (3) 從匯點Vn出發(fā)，令Lvn=evn，按逆拓撲排序的序

50、列求其余各頂點的最遲出現(xiàn)時間 Lvi(n-1i1)； (4) 根據(jù)各頂點的ev和Lv值求每條有向邊ai的最早開始時間ei和最遲開始時間Li。若某有向邊ai滿足ei=Li,則為關鍵活動,.,90,AOE網(wǎng)：帶權的有向圖，其中，頂點表示事件，弧表示活動，權表示活動持續(xù)的時間。 關鍵路徑：AOE-網(wǎng)中有些活動可以并行的進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度（這里所說的長度是指路徑上各個活動持續(xù)時間之和，不是路徑上弧的數(shù)目）。路徑長度最長的路徑叫做關鍵路徑。 最早發(fā)生時間：假設開始點是V1，從V1到Vi的最長的路徑的長度叫做事件Vi的最早發(fā)生時間。 最遲開始時間：不推遲整個工程

51、完成的前提下，活動ai最遲 必須開始進行的時間。 關鍵活動：l（i）=e（i）的活動。,回顧基本概念并練習：,.,91,v1,v3,v8,v9,v7,v2,v6,v4,v5,a3=5,a6=2,a9=4,a11=4,a10=2,a8=7,a4=1,a1=6,a2=4,a5=1,a7=9,如何求關鍵路徑？,如圖所示：,關鍵： 求出各個事件最早出現(xiàn)時間ve（j）和最遲發(fā)生時 間vl（j）。 再判斷各活動e（i）是否等于l（i）！,.,92,1 求事件最早出現(xiàn)時間,v1,v3,v8,v9,v7,v2,v6,v4,v5,a3=5,a6=2,a9=4,a11=4,a10=2,a8=7,a4=1,a1=6

52、,a2=4,a5=1,a7=9,0,6,4,5,7,14,18,7,16,從ve（0）=0開始向后推. Ve（j）=Maxve（i）+dut（i,j） (j=1，2.n-1),.,93,1 求事件最遲出現(xiàn)時間,v1,v3,v8,v9,v7,v2,v6,v4,v5,a3=5,a6=2,a9=4,a11=4,a10=2,a8=7,a4=1,a1=6,a2=4,a5=1,a7=9,0,6,6,8,10,14,18,7,16,從vl(9）=18開始向回推（倒計時）。 Ve（i）=Minvl（j）- dut（i,j） (j=n-2,n-3,-,0),.,94,.,95,由表可知時間余量為零的活動都是關鍵活動，即為a1，a4，a7，a8，a10，a11。 這些關鍵活動構(gòu)成兩條關鍵路徑，即