深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017圖演示文檔

.,第七章圖,數(shù)據(jù)結(jié)構(gòu),.,一、圖的定義(Graph),2,圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph( V, E ) 其中V = x | x數(shù)據(jù)對象是頂點(diǎn)的有窮非空集合 E是頂點(diǎn)之間關(guān)系的有窮集合，包括 E1 = (x, y) | x, y V 邊的集合 或 E2 = | x, y V 弧的集合,第一節(jié)圖的定義與術(shù)語,.,第一節(jié)圖的定義與術(shù)語,交通圖（公路、鐵路） 頂點(diǎn)：地點(diǎn) 邊：連接地點(diǎn)的公路交通圖中有單行道雙行道,分別用有向邊、無向邊表示；電路圖 頂點(diǎn)：元件 邊：連接元件之間的線路通訊線路圖 頂點(diǎn)：地點(diǎn) 邊：地點(diǎn)間的連線,.,二、無向圖(Undigraph),4,第一節(jié)圖的定義與術(shù)語,用(x,y)表示兩個(gè)頂點(diǎn)x,y之間的一條邊(edge)N=V,E，V=0,1,2,3,4,5，E=(0,1), (0,4), (0,5), (1,2), (1,3), (1,5), (2,3), (3,4), (3,5), (4,5),.,二、無向圖(完全圖),5,第一節(jié)圖的定義與術(shù)語,如果無向圖有n(n-1)/2條邊，稱為無向完全圖,.,二、無向圖,6,第一節(jié)圖的定義與術(shù)語,鄰接點(diǎn)：如果(x,y)E,稱x,y互為鄰接點(diǎn)，即x,y相鄰接依附：邊(x,y)依附于頂點(diǎn)x,y相關(guān)聯(lián)：邊(x,y)與x,y相關(guān)聯(lián)頂點(diǎn)的度：和頂點(diǎn)相關(guān)聯(lián)的 邊的數(shù)目，記為TD(x),.,三、有向圖(Digraph),7,第一節(jié)圖的定義與術(shù)語,用表示從x到y(tǒng)的一條弧(Arc)，且稱x為弧尾，y為弧頭，N=V,E，V=0,1,2,3,4，E=， ,.,三、有向圖(完全圖),8,第一節(jié)圖的定義與術(shù)語,如果有向圖有n(n-1)條邊，則稱為有向完全圖,.,三、有向圖,9,第一節(jié)圖的定義與術(shù)語,鄰接：如果E,稱x鄰接到y(tǒng),或y鄰接自x相關(guān)聯(lián)：弧與x,y相關(guān)聯(lián)入度：以頂點(diǎn)為頭的弧的 數(shù)目，記為ID(x)出度：以頂點(diǎn)為尾的弧的 數(shù)目，記為OD(x)度：TD(x)=ID(x)+OD(x),.,四、路徑(Path),10,第一節(jié)圖的定義與術(shù)語,路徑：是一個(gè)從頂點(diǎn)x到y(tǒng)的頂點(diǎn)序列(x, vi1, vi2, vin, y)其中，(x,vi1),(vij-1,vij),(vin,y)皆屬于E,1到3有路徑(1,0,4,3),1到4有路徑(1,2,4),.,五、回路,11,第一節(jié)圖的定義與術(shù)語,回路或環(huán)：路徑的開始頂點(diǎn)與最后一個(gè)頂點(diǎn)相同，即路徑中(x, vi1, vi2, vin, y)，x=y簡單路徑：路徑的頂點(diǎn)序列中，頂點(diǎn)不重復(fù)出現(xiàn),1到1構(gòu)成環(huán)(1,0,4,3,1),1到3是簡單路徑(1,0,4,3),.,六、連通,12,第一節(jié)圖的定義與術(shù)語,連通：如果頂點(diǎn)x到y(tǒng)有路徑，稱x和y是連通的連通圖：圖中所有頂點(diǎn)都連通,連通圖,非連通圖,.,七、子圖,13,第一節(jié)圖的定義與術(shù)語,設(shè)有兩個(gè)圖 G(V, E) 和 G(V, E)。若 V V 且 EE, 稱圖G是圖G的子圖,.,八、生成樹,14,第一節(jié)圖的定義與術(shù)語,一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊,.,第二節(jié)圖的存儲結(jié)構(gòu),圖的鄰接矩陣存儲表示法圖的鄰接表表示法圖的逆鄰接表表示法圖的十字鏈表表示法圖的鄰接多重表表示法,.,一、鄰接矩陣(Adjacency Matrix),16,第二節(jié)圖的存儲結(jié)構(gòu),鄰接矩陣：記錄圖中各頂點(diǎn)之間關(guān)系的二維數(shù)組。對于不帶權(quán)的圖，以1表示兩頂點(diǎn)存在邊(或弧)(相鄰接)，以0表示兩頂點(diǎn)不鄰接，即 1 如果(i,j)E 或 EAij = 0 其它,.,一、鄰接矩陣,17,第二節(jié)圖的存儲結(jié)構(gòu),無向圖的鄰接矩陣為：有向圖的鄰接矩陣為：,.,一、鄰接矩陣(性質(zhì)),18,第二節(jié)圖的存儲結(jié)構(gòu),無向圖的鄰接矩陣是對稱的其第i行1的個(gè)數(shù)或第i列1的個(gè)數(shù)，等于頂點(diǎn)i的度TD(i)有向圖的鄰接矩陣可能是不對稱的其第i行1的個(gè)數(shù)等于頂點(diǎn)i的出度OD(i)，第j列1的個(gè)數(shù)等于頂點(diǎn)j的入度ID(j),.,一、鄰接矩陣(網(wǎng)絡(luò)),19,第二節(jié)圖的存儲結(jié)構(gòu),有時(shí)在圖的每條邊上附上相關(guān)的數(shù)值，這種與圖的邊相關(guān)的數(shù)值叫權(quán)。 權(quán)可以表示兩個(gè)頂點(diǎn)之間的距離、耗費(fèi)等具有某種意義的數(shù),若將圖的每條邊都賦上一個(gè)權(quán)，則稱這種帶權(quán)圖為網(wǎng)絡(luò)。 在網(wǎng)絡(luò)中，兩個(gè)頂點(diǎn)如果不鄰接，則被視為距離為無窮大； wi,j 如果(i,j)E 或 EAij = 其它,.,一、鄰接矩陣(網(wǎng)絡(luò)),20,第二節(jié)圖的存儲結(jié)構(gòu),有向網(wǎng)N=V,E，V=0,1,2,3,4，E=, E中每個(gè)元組的第三個(gè)元素表示權(quán)。 1、畫出該網(wǎng), 2、寫出該網(wǎng)的鄰接矩陣。,.,一、鄰接矩陣(定義),21,第二節(jié)圖的存儲結(jié)構(gòu),#define MAXVERTEXNUM 100 /最大頂點(diǎn)數(shù)typedef struct int VertexNum; /頂點(diǎn)數(shù)char VertexMAXVERTEXNUM;/頂點(diǎn)數(shù)據(jù)int AdjMatrixMAXVERTEXNUMMAXVERTEXNUM; / 鄰接矩陣 Graph;Graph MGraph;,.,一、鄰接矩陣(創(chuàng)建),22,第二節(jié)圖的存儲結(jié)構(gòu),#define INFINITY100/無窮大void CreateGraph(Graph *G) /生成圖int i, j;cin >> G->VertexNum;/輸入圖的頂點(diǎn)數(shù)for (i=1; iVertexNum; i+)cin >> G->Vertexi; /輸入頂點(diǎn)信息for (i=1; iVertexNum; i+) for (j=1; jVertexNum; j+) cin >> G->AdjMatrixij; /依次輸入鄰接矩陣 if (G->AdjMatrixij = -1) G->AdjMatrixij = INFINITY; ,.,二、鄰接表(Adjacency List),23,第二節(jié)圖的存儲結(jié)構(gòu),鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)在鄰接表中，每個(gè)頂點(diǎn)設(shè)置一個(gè)單鏈表，其每個(gè)結(jié)點(diǎn)都是依附于該頂點(diǎn)的邊（或以該頂點(diǎn)為尾的?。?.,二、鄰接表(結(jié)點(diǎn)結(jié)構(gòu)),24,第二節(jié)圖的存儲結(jié)構(gòu),邊(弧)的結(jié)點(diǎn)結(jié)構(gòu) adjvex; / 該邊(弧)所指向的頂點(diǎn)的位置 nextarc;/ 指向下一條邊(弧)指針 info; / 該邊(弧)相關(guān)信息的指針或權(quán)值頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu) data; / 頂點(diǎn)信息 firstarc;/指向第一條依附該頂點(diǎn)的邊(弧),.,typedef struct VexNode / 定義圖的頂點(diǎn) char Vertex;/ 頂點(diǎn)int Weight;/ 邊（?。┑臋?quán)值struct VexNode *NextArc;/ 指向下一條邊(弧)指針 VexNode;,第二節(jié)圖的存儲結(jié)構(gòu),二、鄰接表(結(jié)點(diǎn)結(jié)構(gòu)),.,二、鄰接表(無向圖),26,第二節(jié)圖的存儲結(jié)構(gòu),.,二、鄰接表(有向圖),27,第二節(jié)圖的存儲結(jié)構(gòu),.,二、鄰接表(網(wǎng)絡(luò)),28,第二節(jié)圖的存儲結(jié)構(gòu),.,二、鄰接表(定義),29,第二節(jié)圖的存儲結(jié)構(gòu),typedef struct / 定義圖（采用鄰接鏈表）int VertexNum;/ 頂點(diǎn)數(shù)VexNode *AdjList;/ 鄰接表頭指針 Graph;Graph MGraph;,.,二、鄰接表(創(chuàng)建),30,第二節(jié)圖的存儲結(jié)構(gòu),void CreateGraph(Graph *G)/ 創(chuàng)建圖（鄰接表）int i, ArcNum;char x, y;cin >> G->VertexNum;/ 輸入頂點(diǎn)數(shù)G->AdjList=new VexNodeG->VertexNum+1; / 申請n個(gè)頭結(jié)點(diǎn)for (i=1; iVertexNum; i+) cin >> G->AdjListi.Vertex;/ 輸入頂點(diǎn)信息（字符）G->AdjListi.NextArc=NULL; / 頭頂點(diǎn)下一條邊指針為空 cin >> ArcNum; / 輸入邊（?。?shù)for (i=1; i> x; / 輸入頂點(diǎn)1（或弧尾）cin >> y; / 輸入頂點(diǎn)2（或弧頭）InsertLinkList(G, x, y); / 在x單鏈表中，插入y結(jié)點(diǎn)InsertLinkList(G, y, x); / 插入x結(jié)點(diǎn)（無向圖）,.,二、鄰接表(創(chuàng)建插入結(jié)點(diǎn)),31,第二節(jié)圖的存儲結(jié)構(gòu),void InsertLinkList(Graph *G, char x, char y)int j;VexNode *p, *q;j = GetVexNodeNo(G, x); / 找到頂點(diǎn)x對應(yīng)的單鏈表頭結(jié)點(diǎn)q = new VexNode;/ 申請一個(gè)新結(jié)點(diǎn)q->Vertex = y;/ 邊的另一個(gè)頂點(diǎn)（弧頭）為yq->NextArc = NULL;if (G->AdjListj.NextArc=NULL)|(G->AdjListj.NextArc->Vertex>y)q->NextArc = G->AdjListj.NextArc; / 插入結(jié)點(diǎn)G->AdjListj.NextArc = q;else p = G->AdjListj.NextArc;while(p->NextArc),.,二、鄰接表(創(chuàng)建頂點(diǎn)對應(yīng)的序號),32,第二節(jié)圖的存儲結(jié)構(gòu),int GetVexNodeNo(Graph *G, char c) / 找到字符對應(yīng)的單鏈表序號 int j; for (j=1; jVertexNum; j+) if (G->AdjListj.Vertex = c) break; return(j);,.,二、鄰接表(性質(zhì)),33,第二節(jié)圖的存儲結(jié)構(gòu),有向圖鄰接表: 頂點(diǎn)的出度-第i個(gè)鏈表中結(jié)點(diǎn)的個(gè)數(shù)； 頂點(diǎn)的入度-必須遍歷整個(gè)鄰接表也可以建立一個(gè)逆鄰接表要判定兩個(gè)頂點(diǎn)i和j是否有邊（或?。?，必須搜索整個(gè)第i個(gè)和第j個(gè)鏈表，不及鄰接矩陣方便,.,二、鄰接表(有向圖的逆鄰接表),34,第二節(jié)圖的存儲結(jié)構(gòu),逆鄰接表中，弧的箭頭向內(nèi)(入弧),.,三、十字鏈表(Orthogonal List),35,第二節(jié)圖的存儲結(jié)構(gòu),十字鏈表是有向圖的另一種存儲結(jié)構(gòu)十字鏈表是將有向圖的鄰接表和逆鄰接表結(jié)合起來的一種存儲結(jié)構(gòu),.,三、十字鏈表(結(jié)點(diǎn)結(jié)構(gòu)),36,第二節(jié)圖的存儲結(jié)構(gòu),弧的結(jié)點(diǎn)結(jié)構(gòu) tailvex;/ 弧尾頂點(diǎn)的位置 headvex;/ 弧頭頂點(diǎn)的位置 tlink; / 指向弧尾相同的下一條弧 hlink; / 指向弧頭相同的下一條弧 info; / 該弧相關(guān)信息的指針或權(quán)值,.,三、十字鏈表(結(jié)點(diǎn)結(jié)構(gòu)),37,第二節(jié)圖的存儲結(jié)構(gòu),頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)data; / 與頂點(diǎn)相關(guān)的信息firstin; / 指向以頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)firstout;/ 指向以頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn),.,三、十字鏈表(舉例),38,第二節(jié)圖的存儲結(jié)構(gòu),.,四、鄰接多重表(Adjacency Multilist),39,第二節(jié)圖的存儲結(jié)構(gòu),鄰接多重表是無向圖的另一種存儲結(jié)構(gòu)在無向圖中，一條邊要用2個(gè)結(jié)點(diǎn)表示(分別從2個(gè)頂點(diǎn)的角度看)在鄰接多重表中，一條邊只用一個(gè)結(jié)點(diǎn)表示將所有具有某頂點(diǎn)的結(jié)點(diǎn)，全部用鏈連結(jié)起來，鏈所在的域?yàn)樵擁旤c(diǎn)對應(yīng)的指針域,.,四、鄰接多重表(結(jié)點(diǎn)結(jié)構(gòu)),40,第二節(jié)圖的存儲結(jié)構(gòu),邊的結(jié)點(diǎn)結(jié)構(gòu) mark; / 標(biāo)記域，如指示該邊是否被搜索過 ivex,jvex;/ 該邊所依附的兩個(gè)頂點(diǎn)的位置 ilink;/ 指向下一條依附于ivex的邊 jlink;/ 指向下一條依附于jvex的邊 info; / 該邊相關(guān)信息的指針或權(quán)值,.,四、鄰接多重表(舉例),41,第二節(jié)圖的存儲結(jié)構(gòu),.,一、圖的遍歷,42,第三節(jié)圖的遍歷,從圖的某一頂點(diǎn)開始，訪遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問一次圖的遍歷主要應(yīng)用于無向圖,.,二、深度優(yōu)先搜索(DFS),43,第三節(jié)圖的遍歷,圖的深度優(yōu)先搜索是樹的先根遍歷的推廣圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組 visited ,.,二、深度優(yōu)先搜索(DFS算法),第三節(jié)圖的遍歷,所有頂點(diǎn)訪問標(biāo)志visited設(shè)置為FALSE從某頂點(diǎn)v0開始，設(shè)v=v01.如果visitedv=FALSE，則訪問該頂點(diǎn)，且設(shè)visitedv=TRUE2.如果找到當(dāng)前頂點(diǎn)的一個(gè)新的相鄰頂點(diǎn)w,設(shè)v=w,重復(fù)13.否則(說明當(dāng)前頂點(diǎn)的所有相鄰頂點(diǎn)都已被訪問過，或者當(dāng)前頂點(diǎn)沒有相鄰頂點(diǎn))，如果當(dāng)前頂點(diǎn)是v0，退出；否則返回上一級頂點(diǎn)，重復(fù)2,.,二、深度優(yōu)先搜索(舉例),45,第三節(jié)圖的遍歷,采用以下鏈表存儲結(jié)構(gòu)時(shí)，DFS次序?yàn)?,1,2,3,4,5,visit,.,二、深度優(yōu)先搜索(舉例),46,第三節(jié)圖的遍歷,DFS次序1:V1,V2,V4,V8,V5,V3,V6,V7DFS次序2:V1,V2,V5,V8,V4,V3,V6,V7,由于沒有規(guī)定訪問鄰接點(diǎn)的順序，深度優(yōu)先序列不唯一,.,第三節(jié)圖的遍歷,當(dāng)采用鄰接表存儲結(jié)構(gòu)并且存儲結(jié)構(gòu)已確定的情況下，遍歷的結(jié)果是確定的。,c0,c1,c3,c2,c4,c5,DFS序列：c0 c1 c3 c4 c5 c2,.,三、廣度優(yōu)先搜索(BFS),48,第三節(jié)圖的遍歷,廣度優(yōu)先搜索(BFS)是一種分層搜索方法BFS每向前走一步可能訪問一批頂點(diǎn), 不存在往回退的情況BFS不是一個(gè)遞歸的過程。,.,三、廣度優(yōu)先搜索(BFS算法),49,第三節(jié)圖的遍歷,所有頂點(diǎn)訪問標(biāo)志visited設(shè)置為FALSE從某頂點(diǎn)v0開始，訪問v0，visitedv0=TRUE，將v0插入隊(duì)列Q1.如果隊(duì)列Q不空，則從隊(duì)列Q頭上取出一個(gè)頂點(diǎn)v,否則結(jié)束2.依次找到頂點(diǎn)v的所有相鄰頂點(diǎn)v，如果visitedv=FALSE，訪問該頂點(diǎn)v，visitedv=TRUE，將v插入隊(duì)列Q3.重復(fù)1,2,.,三、廣度優(yōu)先搜索(BFS函數(shù)),50,第三節(jié)圖的遍歷,void BFSTraverse(Graph *G, char FirstVertex)int i, j; char y, VisitedMAXVERTEXNUM;VexNode *p;for (i=1; iVertexNum; i+) Visitedi = F'/ 所有結(jié)點(diǎn)對應(yīng)的訪問位 賦初值InitQueue(GQ); / 清空循環(huán)隊(duì)列i = GetVexNodeNo(G, FirstVertex);Visitedi = 'T'cout AdjListi.Vertex;EnQueue(GQ, G->AdjListi.Vertex); / 新搜索到的結(jié)點(diǎn)插入隊(duì)列while (QueueEmpty(GQ) != ERROR) DeQueue(GQ, ,.,三、廣度優(yōu)先搜索(舉例),第三節(jié)圖的遍歷,BFS為0,1,4,5,2,3 BFS為v1,v2,v3,v4, v5,v6,v7,v8,.,算法分析 DFS遍歷：實(shí)質(zhì)是對每個(gè)頂點(diǎn)查找鄰接點(diǎn)的過程，取決于存儲結(jié)構(gòu)。當(dāng)圖有e條邊，其時(shí)間復(fù)雜度為O(e)，圖的每個(gè)頂點(diǎn)至多調(diào)用一次DFS函數(shù)（遞歸過程）。 總時(shí)間復(fù)雜度為O(n+e) 。 BFS遍歷： 與DFS遍歷唯一區(qū)別是鄰接點(diǎn)搜索次序不同. 總時(shí)間復(fù)雜度為O(n+e) 。,第三節(jié)圖的遍歷,.,練 習(xí),例按順序輸入頂點(diǎn)對：(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)， 根據(jù)建立無向圖的鄰接表算法,畫出相應(yīng)的鄰接表。并寫出在該鄰接表上，從頂點(diǎn)4開始搜索所得的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。,.,一、無向圖的連通性,54,第四節(jié)圖的連通性問題,如果無向圖中，存在不連通的頂點(diǎn)，則該圖稱為非連通圖 非連通圖 連通圖,.,二、無向圖的連通分量,55,第四節(jié)圖的連通性問題,非連通圖的極大連通子圖叫做連通分量若從無向圖的每一個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行DFS或BFS遍歷，可求得無向圖的所有連通分量的生成樹(DFS或BFS生成樹)所有連通分量的生成樹組成了非連通圖的生成森林,.,二、無向圖的生成樹,56,第四節(jié)圖的連通性問題,由DFS遍歷，求得連通分量稱為DFS生成樹由BFS遍歷，求得連通分量稱為BFS生成樹,BFS生成樹,DFS生成樹,.,三、最小生成樹,57,第四節(jié)圖的連通性問題,如果無向圖中，邊上有權(quán)值，則稱該無向圖為無向網(wǎng)如果無向網(wǎng)中的每個(gè)頂點(diǎn)都相通，稱為連通網(wǎng)最小生成樹(Minimum Cost Spanning Tree)是代價(jià)最小的連通網(wǎng)的生成樹，即該生成樹上的邊的權(quán)值和最小,.,三、最小生成樹(準(zhǔn)則),58,第四節(jié)圖的連通性問題,必須使用且僅使用連通網(wǎng)中的n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達(dá)到最小。,.,四、普里姆(Prim)算法生成最小生成樹,59,第四節(jié)圖的連通性問題,假設(shè)N=(V,E)是連通網(wǎng)TE是N上最小生成樹中邊的集合1.U=u0，(u0V), TE=2.在所有uU,vV-U的邊(u,v)E中找一條代價(jià)最小的邊(u,v0)并入集合TE，同時(shí)v0并入U(xiǎn)3.重復(fù)2，直到U=V,.,四、普里姆(Prim)算法舉例,60,第四節(jié)圖的連通性問題,原圖 (a) (b),(c) (d) (e) (f),.,P174頁，圖7.16,.,算法7.9,void MiniSpanTree_PRIM(MGraph G, VertexType u) / 用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，輸出T的各條邊,記錄從頂點(diǎn)集U到VU的代價(jià)最小的邊的輔助數(shù)組定義 struct VertexType adjvex; VRType lowcost; closedgeMAX_VERTEX_NUM; int i,j,k; k = LocateVex ( G, u ); for ( j=0; j0, viV-U printf(closedgek.adjvex, G.vexsk); / 輸出生成樹的邊 closedgek.lowcost = 0; / 第k頂點(diǎn)并入U(xiǎn)集 for (j=0; j<G.vexnum; +j) if (G.arcskj.adj < closedgej.lowcost) / 新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊 / closedgej = G.vexsk, G.arcskj.adj ; closedgej.adjvex=G.vexsk; closedgej.lowcost=G.arcskj.adj; / MiniSpanTree,.,五、克魯斯卡爾(Kruskal)算法生成最小生成樹,63,第四節(jié)圖的連通性問題,假設(shè)N=(V,E)是連通網(wǎng)1.非連通圖T=V,，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量2.在E中找一條代價(jià)最小，且其兩個(gè)頂點(diǎn)分別依附不同的連通分量的邊，將其加入T中3.重復(fù)2，直到T中所有頂點(diǎn)都在同一連通分量上,.,五、克魯斯卡爾(Kruskal)算法舉例,64,第四節(jié)圖的連通性問題,(c) (d) (e) (f),原圖 (a) (b),.,練 習(xí),例無向網(wǎng)N=V,E，V=0,1,2,3,4，E=(0,1,10)，(0,4,19)，(0,2,1)，(0,3,8)，(1,2,5)，(1,3,6)，(1,4,29),(2,3,6)，(3,4,3，E中每個(gè)元組的第三個(gè)元素表示權(quán)。. 畫出該網(wǎng)；. 寫出該網(wǎng)的鄰接矩陣；. 用Prim算法(從頂點(diǎn)0開始)求最小生成樹，依次 寫出樹的生長過程；. 用Kruskal算法求最小生成樹，依次寫出樹的生 長過程。,.,一、最短路徑,66,第五節(jié)最短路徑,最短路徑是求從圖（或網(wǎng)）中某一頂點(diǎn)，到其余各頂點(diǎn)的最短路徑最短路徑與最小生成樹主要有三點(diǎn)不同：1.最短路徑的操作對象主要是有向圖(網(wǎng))，而最小生成樹的操作對象是無向圖2.最短路徑有一個(gè)始點(diǎn)，最小生成樹沒有3.最短路徑關(guān)心的是始點(diǎn)到每個(gè)頂點(diǎn)的路徑最短，而最小生成樹關(guān)心的是整個(gè)樹的代價(jià)最小,.,二、Dijkstra算法,67,第五節(jié)最短路徑,最短路徑可以采用迪杰斯特拉(Dijkstra)算法求解Dijkstra算法采用按路徑長度遞增的次序產(chǎn)生最短路徑,.,二、Dijkstra算法,68,第五節(jié)最短路徑,在Dijkstra算法中，引進(jìn)了一個(gè)輔助向量D每個(gè)分量Di表示當(dāng)前所找到的從始點(diǎn)到每個(gè)終點(diǎn)vi的最短路徑長度Di初值為始點(diǎn)v0到各終點(diǎn)vi的直接距離，即若從始點(diǎn)到某終點(diǎn)有(出)弧，則為弧上的權(quán)值，否則為,.,二、Dijkstra算法,第五節(jié)最短路徑,對于下圖，如果0是始點(diǎn)v0，則Di的初值為：Di=5,7,15顯然， Dj=MinDi | viV 是從始點(diǎn)出發(fā)的長度最短的 一條最短路徑,.,二、Dijkstra算法,第五節(jié)最短路徑,設(shè)S為已求得的最短路徑的終點(diǎn)的集合下一條最短路徑(設(shè)其終點(diǎn)為vi)為以下之一：1.中間只經(jīng)過S中的頂點(diǎn)而后到達(dá)頂點(diǎn)vi的路徑2.弧Dj=MinDi | viV-S Dk= or Di=Dj+,.,二、Dijkstra算法,第五節(jié)最短路徑,1. 初始化： S v0 ; Di arc0i, i = 1, 2, , n-1;2. 求出最短路徑的長度： Dj min Di , i V-S ; SS U j ;3. 修改： Di minDi, Dj + arcji , iV-S 4. 判斷：若 S = V, 則算法結(jié)束，否則轉(zhuǎn) 2。,71,.,二、Dijkstra算法,第五節(jié)最短路徑,.,第五節(jié)最短路徑,舉例:如圖所示帶權(quán)有向圖,用Dijkstra算法求(1)從頂點(diǎn)0到其它頂點(diǎn)的最短路徑及S、U、和0到各頂點(diǎn)的距離變化情況. S U 0到各頂點(diǎn)的距離 終點(diǎn)0 1,2,3,4,5,6 0,4,6,6, , 10,1 2,3,4,5,6 0,4,5,6,11, , 20,1,2 3,4,5,6 0,4,5,6,11, 9, 3 0,1,2,3 4,5,6 0,4,5,6,11, 9, 50,1,2,3,5 4,6 0,4,5,6,10, 9, 17 40,1,2,3,5,4 6 0,4,5,6,10, 9, 16 60,1,2,3,5,4,6 0,4,5,6,10, 9, 16,.,第五節(jié)最短路徑,（2）計(jì)算過程：(1)初值：s=0,dist=0, 4, 6, 6, , , path=0, 0, 0, 0, -1, -1, -1(2) s=0,1,從頂點(diǎn)1到達(dá)頂點(diǎn)2和4 dist2=mindist2,dist1+1=5(修改) dist4=mindist4,dist1+7=11(修改) 則 : dist=0, 4, 5, 6, 11, , path=0, 0, 1, 0, 1, -1 ,-1（3）s=0,1,2,從頂點(diǎn)2到達(dá)頂點(diǎn)4和5 dist4=mindist4,dist2+6=11 dist5=mindist5,dist2+4=9(修改) 則 : dist= 0, 4, 5, 6, 11, 9, path=0, 0, 1, 0, 1, 2, -1,.,第五節(jié)最短路徑,（4）s=0,1,2,3,從頂點(diǎn)3到達(dá)頂點(diǎn)2和5 dist2=mindist2,dist3+2=5 dist5=mindist5,dist3+5=9 則 ：沒有修改，dist 、 path不變（5）s=0,1,2,3,5,從頂點(diǎn)5到達(dá)頂點(diǎn)4和6 dist4=mindist4,dist5+1=10 (修改) dist6=mindist6,dist5+8=17(修改) 則 :dist=0, 4, 5, 6, 10, 9, 17 path= 0, 0,1, 0, 5, 2, 5(6) s=0,1,2,3,5,4,從頂點(diǎn)4到達(dá)頂點(diǎn)6 dist6=mindist6,dist4+6=16(修改) 則 ：dist=0, 4, 5, 6, 10, 9, 16 path=0, 0, 1, 0, 5, 2, 4(7) s=0,1,2,3,5,4,6,從頂點(diǎn)6不能到達(dá)任何頂點(diǎn)，算法結(jié)束。 則 ：dist=0, 4, 5, 6, 10, 9, 16 path=0, 0, 1, 0, 5, 2, 4,.,三、Dijkstra算法代碼,第五節(jié)最短路徑,char PathMAXVERTEXNUMMAXVERTEXNUM; / 采用順序表，存放每個(gè)結(jié)點(diǎn)對應(yīng)的最短路徑int DestMAXVERTEXNUM;void ShortestPath(Graph *G, char StartVexChar)int i, j, m, StartVex, CurrentVex, MinDest;int FinalMAXVERTEXNUM;for (i=1; iVertexNum; i+) / 找到開始頂點(diǎn)的序號 if (G->Vertexi = StartVexChar) StartVex = i; break;for (i=1; iVertexNum; i+) Pathi0 = 0; / 順序表的0位置，存放順序表(路徑)的長度 Desti = INFINITY;/ 所有頂點(diǎn)到開始頂點(diǎn)之間的距離初值設(shè)為無窮大 if (G->AdjMatrixStartVexi AdjMatrixStartVexi; Pathi1 = G->VertexStartVex; Pathi2 = G->Vertexi; Pathi0 = 2; Finali = 'F',76,.,三、Dijkstra算法代碼,第五節(jié)最短路徑,DestStartVex = 0; / 初始化，開始頂點(diǎn)屬于S集（已處理過的結(jié)點(diǎn)）FinalStartVex = 'T'for (i=1; iVertexNum; i+) MinDest = INFINITY; for (j=1; jVertexNum; j+) / 找未處理頂點(diǎn)中到開始頂點(diǎn)最近的頂點(diǎn) if (Finalj = 'F') if (Destj VertexNum; j+) / 更新當(dāng)前最短路徑及距離 if(Finalj='F') ,77,.,一、有向無環(huán)圖(DAG),第六節(jié)有向無環(huán)圖及其應(yīng)用,有向無環(huán)圖(DAG:Directed Acycline Graph)是圖中無環(huán)的有向圖,DAG,非DAG,78,.,一、有向無環(huán)圖(DAG),第六節(jié)有向無環(huán)圖及其應(yīng)用,有向圖中，可以用深度優(yōu)先搜索(DFS)，找出是否存在環(huán)從某個(gè)頂點(diǎn)v出發(fā)，進(jìn)行DFS，如果存在一條從頂點(diǎn)u到v的回邊，則有向圖中存在環(huán)DFS: 0,1,2,4,3,非DAG,.,二、拓?fù)渑判?第六節(jié)有向無環(huán)圖及其應(yīng)用,1.偏序若集合X上的關(guān)系R是：.自反的：x R x.反對稱的：x R y => y R x.傳遞的：xRy & yRz => xRz 則稱R是集合X上的偏序關(guān)系,.,二、拓?fù)渑判?第六節(jié)有向無環(huán)圖及其應(yīng)用,2.全序設(shè)關(guān)系R是集合X上的偏序，如果對每個(gè)x,yX，必有xRy或者yRx，則稱R是X上的全序關(guān)系偏序指集合中僅有部分成員之間可比較全序指集合中全體成員之間均可比較,81,.,二、拓?fù)渑判?第六節(jié)有向無環(huán)圖及其應(yīng)用,3.拓?fù)溆行蛴覉D是一個(gè)偏序關(guān)系，因?yàn)?,3沒有先后關(guān)系如果人為地增加1,3先后關(guān)系，如1先于3，則右圖變?yōu)槿颍?稱為拓?fù)溆行?.,二、拓?fù)渑判?第六節(jié)有向無環(huán)圖及其應(yīng)用,4.拓?fù)渑判蛴善蚨x得到的拓?fù)溆行虻牟僮鞣Q拓?fù)渑判蛩惴ǎ?在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之.從圖中刪除該頂點(diǎn)和所有以它為尾的弧 重復(fù)兩步，直到所有頂點(diǎn)輸出為止,83,.,第六節(jié)有向無環(huán)圖及其應(yīng)用,算法7.12:Status ToplogicalSort(ALGraph G) /ToplogicalSort() functionFindInDegree(G,indegree); /Find indegree of node0.vexnum-1InitStack(S);for(i=0;inextarc) k=p->adjvex; if(!(-indegreek) Push(S,k);/end of for/end of whileif (count<G.vexnum) return (ERROR);else return (OK);/end of ToptlogicalSort() function,.,二、拓?fù)渑判?舉例),第六節(jié)有向無環(huán)圖及其應(yīng)用,原圖,輸出0之后,輸出0,1之后,輸出0,1,3之后,4,最后輸出拓?fù)渑判蚪Y(jié)果：0,1,3,2,4,輸出0,1,3,2之后,.,三、AOV-網(wǎng),第六節(jié)有向無環(huán)圖及其應(yīng)用,如果用有向圖的頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系，則稱該有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)AOV(Activity On Vertex Network)AOV一定是DAG，即圖中不存在環(huán)，因?yàn)榇嬖诃h(huán)意味著某項(xiàng)活動(dòng)應(yīng)以自己為先決條件,86,.,三、AOV-網(wǎng)(舉例),第六節(jié)有向無環(huán)圖及其應(yīng)用,課程代號 課程名稱 先修課程C1 高等數(shù)學(xué)C2 程序設(shè)計(jì)基礎(chǔ)C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2C5 高級語言程序設(shè)計(jì) C2C6 編譯方法 C5, C4C7 操作系統(tǒng) C4, C9C8 普通物理 C1C9 計(jì)算機(jī)原理 C8拓?fù)渑判蚪Y(jié)果為 C1 , C2 , C3 , C4 , C5 , C6, C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6,87,.,四、AOE-網(wǎng),第六節(jié)有向無環(huán)圖及其應(yīng)用,如果用有向圖的頂點(diǎn)表示事件，用弧表示活動(dòng)，則稱該有向圖為邊表示活動(dòng)的網(wǎng)AOE(Activity On Edge)AOE同樣是DAGAOE包括估算工程的完成時(shí)間,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,求工程的完成時(shí)間是AOE的一個(gè)應(yīng)用在工程問題中，需要研究的問題有：.完成整個(gè)工程至少需要多少時(shí)間？.哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？,89,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,1.關(guān)鍵路徑工程問題的AOE網(wǎng)中，從工程開始(頂點(diǎn))到工程結(jié)束(頂點(diǎn))之間路徑長度最長的路徑叫關(guān)鍵路徑提前完成關(guān)鍵路徑上的活動(dòng)，工程進(jìn)度會加快提前完成非關(guān)鍵路徑上的活動(dòng)，對工程無幫助,90,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,2.關(guān)鍵活動(dòng)關(guān)鍵路徑上的所有活動(dòng)稱為關(guān)鍵活動(dòng)找到工程AOE中的所有關(guān)鍵活動(dòng)，即找到了關(guān)鍵路徑,91,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,3.關(guān)鍵活動(dòng)有關(guān)的量e(i)：活動(dòng)ai最早開始時(shí)間l(i)：活動(dòng)ai最遲開始時(shí)間l(i)-e(i)：活動(dòng)ai開始時(shí)間余量如果l(i)=e(i)，則稱活動(dòng)ai為關(guān)鍵活動(dòng),92,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,3.關(guān)鍵活動(dòng)有關(guān)的量ve(j)：事件vj最早開始時(shí)間vl(j)：事件vj最遲開始時(shí)間e(i)=ve(j)l(j)=vl(k)-dut() dut()為活動(dòng)ai的持續(xù)時(shí)間,93,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,3.關(guān)鍵活動(dòng)有關(guān)的量從ve(0)=0開始向前遞推 ve(j)=Maxve(i)+dut() T，T是所有以第j個(gè)頂點(diǎn)為頭的弧的集合從vl(n-1)=ve(n-1)起向后遞推 vl(i)=Minvl(j)-dut() S，S是所有以第i個(gè)頂點(diǎn)為尾的弧的集合,94,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,4.求關(guān)鍵活動(dòng)算法從始點(diǎn)v0出發(fā)，令ve0=0，按拓?fù)溆行蚯髒ej從終點(diǎn)vn-1出發(fā)，令vln-1=ven-1，按逆拓?fù)溆行蚯髒li根據(jù)各頂點(diǎn)的ve和vl值，求每條弧(活動(dòng))ai的最早開始時(shí)間eai和最遲開始時(shí)間lai如果eai=lai，則ai為關(guān)鍵活動(dòng),95,.,五、關(guān)鍵路徑(舉例),第六節(jié)有向無環(huán)圖及其應(yīng)用,ve(j)=Maxve(i)+dut() vl(i)=Minvl(j)-dut()e(i)=ve(j) l(j)=vl(k)-dut()拓?fù)溆行?,1,3,2,4,