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

.,第七章圖,數(shù)據(jù)結(jié)構(gòu),.,一、圖的定義(Graph),2,圖是由頂點集合(vertex)及頂點間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph( V, E ) 其中V = x | x數(shù)據(jù)對象是頂點的有窮非空集合 E是頂點之間關(guān)系的有窮集合，包括 E1 = (x, y) | x, y V 邊的集合 或 E2 = | x, y V 弧的集合,第一節(jié)圖的定義與術(shù)語,.,第一節(jié)圖的定義與術(shù)語,交通圖（公路、鐵路） 頂點：地點 邊：連接地點的公路交通圖中有單行道雙行道,分別用有向邊、無向邊表示；電路圖 頂點：元件 邊：連接元件之間的線路通訊線路圖 頂點：地點 邊：地點間的連線,.,二、無向圖(Undigraph),4,第一節(jié)圖的定義與術(shù)語,用(x,y)表示兩個頂點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ù)語,鄰接點：如果(x,y)E,稱x,y互為鄰接點，即x,y相鄰接依附：邊(x,y)依附于頂點x,y相關(guān)聯(lián)：邊(x,y)與x,y相關(guān)聯(liá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)入度：以頂點為頭的弧的 數(shù)目，記為ID(x)出度：以頂點為尾的弧的 數(shù)目，記為OD(x)度：TD(x)=ID(x)+OD(x),.,四、路徑(Path),10,第一節(jié)圖的定義與術(shù)語,路徑：是一個從頂點x到y(tǒng)的頂點序列(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)：路徑的開始頂點與最后一個頂點相同，即路徑中(x, vi1, vi2, vin, y)，x=y簡單路徑：路徑的頂點序列中，頂點不重復(fù)出現(xiàn),1到1構(gòu)成環(huán)(1,0,4,3,1),1到3是簡單路徑(1,0,4,3),.,六、連通,12,第一節(jié)圖的定義與術(shù)語,連通：如果頂點x到y(tǒng)有路徑，稱x和y是連通的連通圖：圖中所有頂點都連通,連通圖,非連通圖,.,七、子圖,13,第一節(jié)圖的定義與術(shù)語,設(shè)有兩個圖 G(V, E) 和 G(V, E)。若 V V 且 EE, 稱圖G是圖G的子圖,.,八、生成樹,14,第一節(jié)圖的定義與術(shù)語,一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部n個頂點，但只有足以構(gòu)成一棵樹的n-1條邊,.,第二節(jié)圖的存儲結(jié)構(gòu),圖的鄰接矩陣存儲表示法圖的鄰接表表示法圖的逆鄰接表表示法圖的十字鏈表表示法圖的鄰接多重表表示法,.,一、鄰接矩陣(Adjacency Matrix),16,第二節(jié)圖的存儲結(jié)構(gòu),鄰接矩陣：記錄圖中各頂點之間關(guān)系的二維數(shù)組。對于不帶權(quán)的圖，以1表示兩頂點存在邊(或弧)(相鄰接)，以0表示兩頂點不鄰接，即 1 如果(i,j)E 或 EAij = 0 其它,.,一、鄰接矩陣,17,第二節(jié)圖的存儲結(jié)構(gòu),無向圖的鄰接矩陣為：有向圖的鄰接矩陣為：,.,一、鄰接矩陣(性質(zhì)),18,第二節(jié)圖的存儲結(jié)構(gòu),無向圖的鄰接矩陣是對稱的其第i行1的個數(shù)或第i列1的個數(shù)，等于頂點i的度TD(i)有向圖的鄰接矩陣可能是不對稱的其第i行1的個數(shù)等于頂點i的出度OD(i)，第j列1的個數(shù)等于頂點j的入度ID(j),.,一、鄰接矩陣(網(wǎng)絡(luò)),19,第二節(jié)圖的存儲結(jié)構(gòu),有時在圖的每條邊上附上相關(guān)的數(shù)值，這種與圖的邊相關(guān)的數(shù)值叫權(quán)。 權(quán)可以表示兩個頂點之間的距離、耗費等具有某種意義的數(shù),若將圖的每條邊都賦上一個權(quán)，則稱這種帶權(quán)圖為網(wǎng)絡(luò)。 在網(wǎng)絡(luò)中，兩個頂點如果不鄰接，則被視為距離為無窮大； 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中每個元組的第三個元素表示權(quán)。 1、畫出該網(wǎng), 2、寫出該網(wǎng)的鄰接矩陣。,.,一、鄰接矩陣(定義),21,第二節(jié)圖的存儲結(jié)構(gòu),#define MAXVERTEXNUM 100 /最大頂點數(shù)typedef struct int VertexNum; /頂點數(shù)char VertexMAXVERTEXNUM;/頂點數(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;/輸入圖的頂點數(shù)for (i=1; iVertexNum; i+)cin >> G->Vertexi; /輸入頂點信息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)在鄰接表中，每個頂點設(shè)置一個單鏈表，其每個結(jié)點都是依附于該頂點的邊（或以該頂點為尾的?。?.,二、鄰接表(結(jié)點結(jié)構(gòu)),24,第二節(jié)圖的存儲結(jié)構(gòu),邊(弧)的結(jié)點結(jié)構(gòu) adjvex; / 該邊(弧)所指向的頂點的位置 nextarc;/ 指向下一條邊(弧)指針 info; / 該邊(弧)相關(guān)信息的指針或權(quán)值頂點的結(jié)點結(jié)構(gòu) data; / 頂點信息 firstarc;/指向第一條依附該頂點的邊(弧),.,typedef struct VexNode / 定義圖的頂點 char Vertex;/ 頂點int Weight;/ 邊（?。┑臋?quán)值struct VexNode *NextArc;/ 指向下一條邊(弧)指針 VexNode;,第二節(jié)圖的存儲結(jié)構(gòu),二、鄰接表(結(jié)點結(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;/ 頂點數(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;/ 輸入頂點數(shù)G->AdjList=new VexNodeG->VertexNum+1; / 申請n個頭結(jié)點for (i=1; iVertexNum; i+) cin >> G->AdjListi.Vertex;/ 輸入頂點信息（字符）G->AdjListi.NextArc=NULL; / 頭頂點下一條邊指針為空 cin >> ArcNum; / 輸入邊（?。?shù)for (i=1; i> x; / 輸入頂點1（或弧尾）cin >> y; / 輸入頂點2（或弧頭）InsertLinkList(G, x, y); / 在x單鏈表中，插入y結(jié)點InsertLinkList(G, y, x); / 插入x結(jié)點（無向圖）,.,二、鄰接表(創(chuàng)建插入結(jié)點),31,第二節(jié)圖的存儲結(jié)構(gòu),void InsertLinkList(Graph *G, char x, char y)int j;VexNode *p, *q;j = GetVexNodeNo(G, x); / 找到頂點x對應(yīng)的單鏈表頭結(jié)點q = new VexNode;/ 申請一個新結(jié)點q->Vertex = y;/ 邊的另一個頂點（弧頭）為yq->NextArc = NULL;if (G->AdjListj.NextArc=NULL)|(G->AdjListj.NextArc->Vertex>y)q->NextArc = G->AdjListj.NextArc; / 插入結(jié)點G->AdjListj.NextArc = q;else p = G->AdjListj.NextArc;while(p->NextArc),.,二、鄰接表(創(chuàng)建頂點對應(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),有向圖鄰接表: 頂點的出度-第i個鏈表中結(jié)點的個數(shù)； 頂點的入度-必須遍歷整個鄰接表也可以建立一個逆鄰接表要判定兩個頂點i和j是否有邊（或?。仨毸阉髡麄€第i個和第j個鏈表，不及鄰接矩陣方便,.,二、鄰接表(有向圖的逆鄰接表),34,第二節(jié)圖的存儲結(jié)構(gòu),逆鄰接表中，弧的箭頭向內(nèi)(入弧),.,三、十字鏈表(Orthogonal List),35,第二節(jié)圖的存儲結(jié)構(gòu),十字鏈表是有向圖的另一種存儲結(jié)構(gòu)十字鏈表是將有向圖的鄰接表和逆鄰接表結(jié)合起來的一種存儲結(jié)構(gòu),.,三、十字鏈表(結(jié)點結(jié)構(gòu)),36,第二節(jié)圖的存儲結(jié)構(gòu),弧的結(jié)點結(jié)構(gòu) tailvex;/ 弧尾頂點的位置 headvex;/ 弧頭頂點的位置 tlink; / 指向弧尾相同的下一條弧 hlink; / 指向弧頭相同的下一條弧 info; / 該弧相關(guān)信息的指針或權(quán)值,.,三、十字鏈表(結(jié)點結(jié)構(gòu)),37,第二節(jié)圖的存儲結(jié)構(gòu),頂點的結(jié)點結(jié)構(gòu)data; / 與頂點相關(guān)的信息firstin; / 指向以頂點為弧頭的第一個弧結(jié)點firstout;/ 指向以頂點為弧尾的第一個弧結(jié)點,.,三、十字鏈表(舉例),38,第二節(jié)圖的存儲結(jié)構(gòu),.,四、鄰接多重表(Adjacency Multilist),39,第二節(jié)圖的存儲結(jié)構(gòu),鄰接多重表是無向圖的另一種存儲結(jié)構(gòu)在無向圖中，一條邊要用2個結(jié)點表示(分別從2個頂點的角度看)在鄰接多重表中，一條邊只用一個結(jié)點表示將所有具有某頂點的結(jié)點，全部用鏈連結(jié)起來，鏈所在的域為該頂點對應(yīng)的指針域,.,四、鄰接多重表(結(jié)點結(jié)構(gòu)),40,第二節(jié)圖的存儲結(jié)構(gòu),邊的結(jié)點結(jié)構(gòu) mark; / 標(biāo)記域，如指示該邊是否被搜索過 ivex,jvex;/ 該邊所依附的兩個頂點的位置 ilink;/ 指向下一條依附于ivex的邊 jlink;/ 指向下一條依附于jvex的邊 info; / 該邊相關(guān)信息的指針或權(quán)值,.,四、鄰接多重表(舉例),41,第二節(jié)圖的存儲結(jié)構(gòu),.,一、圖的遍歷,42,第三節(jié)圖的遍歷,從圖的某一頂點開始，訪遍圖中其余頂點，且使每一個頂點僅被訪問一次圖的遍歷主要應(yīng)用于無向圖,.,二、深度優(yōu)先搜索(DFS),43,第三節(jié)圖的遍歷,圖的深度優(yōu)先搜索是樹的先根遍歷的推廣圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。為了避免重復(fù)訪問，可設(shè)置一個標(biāo)志頂點是否被訪問過的輔助數(shù)組 visited ,.,二、深度優(yōu)先搜索(DFS算法),第三節(jié)圖的遍歷,所有頂點訪問標(biāo)志visited設(shè)置為FALSE從某頂點v0開始，設(shè)v=v01.如果visitedv=FALSE，則訪問該頂點，且設(shè)visitedv=TRUE2.如果找到當(dāng)前頂點的一個新的相鄰頂點w,設(shè)v=w,重復(fù)13.否則(說明當(dāng)前頂點的所有相鄰頂點都已被訪問過，或者當(dāng)前頂點沒有相鄰頂點)，如果當(dāng)前頂點是v0，退出；否則返回上一級頂點，重復(fù)2,.,二、深度優(yōu)先搜索(舉例),45,第三節(jié)圖的遍歷,采用以下鏈表存儲結(jié)構(gòu)時，DFS次序為0,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ī)定訪問鄰接點的順序，深度優(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每向前走一步可能訪問一批頂點, 不存在往回退的情況BFS不是一個遞歸的過程。,.,三、廣度優(yōu)先搜索(BFS算法),49,第三節(jié)圖的遍歷,所有頂點訪問標(biāo)志visited設(shè)置為FALSE從某頂點v0開始，訪問v0，visitedv0=TRUE，將v0插入隊列Q1.如果隊列Q不空，則從隊列Q頭上取出一個頂點v,否則結(jié)束2.依次找到頂點v的所有相鄰頂點v，如果visitedv=FALSE，訪問該頂點v，visitedv=TRUE，將v插入隊列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é)點對應(yīng)的訪問位 賦初值InitQueue(GQ); / 清空循環(huán)隊列i = GetVexNodeNo(G, FirstVertex);Visitedi = 'T'cout AdjListi.Vertex;EnQueue(GQ, G->AdjListi.Vertex); / 新搜索到的結(jié)點插入隊列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遍歷：實質(zhì)是對每個頂點查找鄰接點的過程，取決于存儲結(jié)構(gòu)。當(dāng)圖有e條邊，其時間復(fù)雜度為O(e)，圖的每個頂點至多調(diào)用一次DFS函數(shù)（遞歸過程）。 總時間復(fù)雜度為O(n+e) 。 BFS遍歷： 與DFS遍歷唯一區(qū)別是鄰接點搜索次序不同. 總時間復(fù)雜度為O(n+e) 。,第三節(jié)圖的遍歷,.,練 習(xí),例按順序輸入頂點對：(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)的鄰接表。并寫出在該鄰接表上，從頂點4開始搜索所得的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。,.,一、無向圖的連通性,54,第四節(jié)圖的連通性問題,如果無向圖中，存在不連通的頂點，則該圖稱為非連通圖 非連通圖 連通圖,.,二、無向圖的連通分量,55,第四節(jié)圖的連通性問題,非連通圖的極大連通子圖叫做連通分量若從無向圖的每一個連通分量中的一個頂點出發(fā)進行DFS或BFS遍歷，可求得無向圖的所有連通分量的生成樹(DFS或BFS生成樹)所有連通分量的生成樹組成了非連通圖的生成森林,.,二、無向圖的生成樹,56,第四節(jié)圖的連通性問題,由DFS遍歷，求得連通分量稱為DFS生成樹由BFS遍歷，求得連通分量稱為BFS生成樹,BFS生成樹,DFS生成樹,.,三、最小生成樹,57,第四節(jié)圖的連通性問題,如果無向圖中，邊上有權(quán)值，則稱該無向圖為無向網(wǎng)如果無向網(wǎng)中的每個頂點都相通，稱為連通網(wǎng)最小生成樹(Minimum Cost Spanning Tree)是代價最小的連通網(wǎng)的生成樹，即該生成樹上的邊的權(quán)值和最小,.,三、最小生成樹(準(zhǔn)則),58,第四節(jié)圖的連通性問題,必須使用且僅使用連通網(wǎng)中的n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個頂點；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達到最小。,.,四、普里姆(Prim)算法生成最小生成樹,59,第四節(jié)圖的連通性問題,假設(shè)N=(V,E)是連通網(wǎng)TE是N上最小生成樹中邊的集合1.U=u0，(u0V), TE=2.在所有uU,vV-U的邊(u,v)E中找一條代價最小的邊(u,v0)并入集合TE，同時v0并入U3.重復(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個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，輸出T的各條邊,記錄從頂點集U到VU的代價最小的邊的輔助數(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頂點并入U集 for (j=0; j<G.vexnum; +j) if (G.arcskj.adj < closedgej.lowcost) / 新頂點并入U后重新選擇最小邊 / 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,，圖中每個頂點自成一個連通分量2.在E中找一條代價最小，且其兩個頂點分別依附不同的連通分量的邊，將其加入T中3.重復(fù)2，直到T中所有頂點都在同一連通分量上,.,五、克魯斯卡爾(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中每個元組的第三個元素表示權(quán)。. 畫出該網(wǎng)；. 寫出該網(wǎng)的鄰接矩陣；. 用Prim算法(從頂點0開始)求最小生成樹，依次 寫出樹的生長過程；. 用Kruskal算法求最小生成樹，依次寫出樹的生 長過程。,.,一、最短路徑,66,第五節(jié)最短路徑,最短路徑是求從圖（或網(wǎng)）中某一頂點，到其余各頂點的最短路徑最短路徑與最小生成樹主要有三點不同：1.最短路徑的操作對象主要是有向圖(網(wǎng))，而最小生成樹的操作對象是無向圖2.最短路徑有一個始點，最小生成樹沒有3.最短路徑關(guān)心的是始點到每個頂點的路徑最短，而最小生成樹關(guān)心的是整個樹的代價最小,.,二、Dijkstra算法,67,第五節(jié)最短路徑,最短路徑可以采用迪杰斯特拉(Dijkstra)算法求解Dijkstra算法采用按路徑長度遞增的次序產(chǎn)生最短路徑,.,二、Dijkstra算法,68,第五節(jié)最短路徑,在Dijkstra算法中，引進了一個輔助向量D每個分量Di表示當(dāng)前所找到的從始點到每個終點vi的最短路徑長度Di初值為始點v0到各終點vi的直接距離，即若從始點到某終點有(出)弧，則為弧上的權(quán)值，否則為,.,二、Dijkstra算法,第五節(jié)最短路徑,對于下圖，如果0是始點v0，則Di的初值為：Di=5,7,15顯然， Dj=MinDi | viV 是從始點出發(fā)的長度最短的 一條最短路徑,.,二、Dijkstra算法,第五節(jié)最短路徑,設(shè)S為已求得的最短路徑的終點的集合下一條最短路徑(設(shè)其終點為vi)為以下之一：1.中間只經(jīng)過S中的頂點而后到達頂點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)從頂點0到其它頂點的最短路徑及S、U、和0到各頂點的距離變化情況. S U 0到各頂點的距離 終點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）計算過程：(1)初值：s=0,dist=0, 4, 6, 6, , , path=0, 0, 0, 0, -1, -1, -1(2) s=0,1,從頂點1到達頂點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,從頂點2到達頂點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,從頂點3到達頂點2和5 dist2=mindist2,dist3+2=5 dist5=mindist5,dist3+5=9 則 ：沒有修改，dist 、 path不變（5）s=0,1,2,3,5,從頂點5到達頂點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,從頂點4到達頂點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,從頂點6不能到達任何頂點，算法結(jié)束。 則 ：dist=0, 4, 5, 6, 10, 9, 16 path=0, 0, 1, 0, 5, 2, 4,.,三、Dijkstra算法代碼,第五節(jié)最短路徑,char PathMAXVERTEXNUMMAXVERTEXNUM; / 采用順序表，存放每個結(jié)點對應(yīng)的最短路徑int DestMAXVERTEXNUM;void ShortestPath(Graph *G, char StartVexChar)int i, j, m, StartVex, CurrentVex, MinDest;int FinalMAXVERTEXNUM;for (i=1; iVertexNum; i+) / 找到開始頂點的序號 if (G->Vertexi = StartVexChar) StartVex = i; break;for (i=1; iVertexNum; i+) Pathi0 = 0; / 順序表的0位置，存放順序表(路徑)的長度 Desti = INFINITY;/ 所有頂點到開始頂點之間的距離初值設(shè)為無窮大 if (G->AdjMatrixStartVexi AdjMatrixStartVexi; Pathi1 = G->VertexStartVex; Pathi2 = G->Vertexi; Pathi0 = 2; Finali = 'F',76,.,三、Dijkstra算法代碼,第五節(jié)最短路徑,DestStartVex = 0; / 初始化，開始頂點屬于S集（已處理過的結(jié)點）FinalStartVex = 'T'for (i=1; iVertexNum; i+) MinDest = INFINITY; for (j=1; jVertexNum; j+) / 找未處理頂點中到開始頂點最近的頂點 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)從某個頂點v出發(fā)，進行DFS，如果存在一條從頂點u到v的回邊，則有向圖中存在環(huán)DFS: 0,1,2,4,3,非DAG,.,二、拓撲排序,第六節(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)系,.,二、拓撲排序,第六節(jié)有向無環(huán)圖及其應(yīng)用,2.全序設(shè)關(guān)系R是集合X上的偏序，如果對每個x,yX，必有xRy或者yRx，則稱R是X上的全序關(guān)系偏序指集合中僅有部分成員之間可比較全序指集合中全體成員之間均可比較,81,.,二、拓撲排序,第六節(jié)有向無環(huán)圖及其應(yīng)用,3.拓撲有序右圖是一個偏序關(guān)系，因為1,3沒有先后關(guān)系如果人為地增加1,3先后關(guān)系，如1先于3，則右圖變?yōu)槿颍?稱為拓撲有序,.,二、拓撲排序,第六節(jié)有向無環(huán)圖及其應(yīng)用,4.拓撲排序由偏序定義得到的拓撲有序的操作稱拓撲排序算法：.在有向圖中選一個沒有前驅(qū)的頂點且輸出之.從圖中刪除該頂點和所有以它為尾的弧 重復(fù)兩步，直到所有頂點輸出為止,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,.,二、拓撲排序(舉例),第六節(jié)有向無環(huán)圖及其應(yīng)用,原圖,輸出0之后,輸出0,1之后,輸出0,1,3之后,4,最后輸出拓撲排序結(jié)果：0,1,3,2,4,輸出0,1,3,2之后,.,三、AOV-網(wǎng),第六節(jié)有向無環(huán)圖及其應(yīng)用,如果用有向圖的頂點表示活動，用弧表示活動間的優(yōu)先關(guān)系，則稱該有向圖為頂點表示活動的網(wǎng)AOV(Activity On Vertex Network)AOV一定是DAG，即圖中不存在環(huán)，因為存在環(huán)意味著某項活動應(yīng)以自己為先決條件,86,.,三、AOV-網(wǎng)(舉例),第六節(jié)有向無環(huán)圖及其應(yīng)用,課程代號 課程名稱 先修課程C1 高等數(shù)學(xué)C2 程序設(shè)計基礎(chǔ)C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2C5 高級語言程序設(shè)計 C2C6 編譯方法 C5, C4C7 操作系統(tǒng) C4, C9C8 普通物理 C1C9 計算機原理 C8拓撲排序結(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)用,如果用有向圖的頂點表示事件，用弧表示活動，則稱該有向圖為邊表示活動的網(wǎng)AOE(Activity On Edge)AOE同樣是DAGAOE包括估算工程的完成時間,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,求工程的完成時間是AOE的一個應(yīng)用在工程問題中，需要研究的問題有：.完成整個工程至少需要多少時間？.哪些活動是影響工程進度的關(guān)鍵？,89,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,1.關(guān)鍵路徑工程問題的AOE網(wǎng)中，從工程開始(頂點)到工程結(jié)束(頂點)之間路徑長度最長的路徑叫關(guān)鍵路徑提前完成關(guān)鍵路徑上的活動，工程進度會加快提前完成非關(guān)鍵路徑上的活動，對工程無幫助,90,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,2.關(guān)鍵活動關(guān)鍵路徑上的所有活動稱為關(guān)鍵活動找到工程AOE中的所有關(guān)鍵活動，即找到了關(guān)鍵路徑,91,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,3.關(guān)鍵活動有關(guān)的量e(i)：活動ai最早開始時間l(i)：活動ai最遲開始時間l(i)-e(i)：活動ai開始時間余量如果l(i)=e(i)，則稱活動ai為關(guān)鍵活動,92,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,3.關(guān)鍵活動有關(guān)的量ve(j)：事件vj最早開始時間vl(j)：事件vj最遲開始時間e(i)=ve(j)l(j)=vl(k)-dut() dut()為活動ai的持續(xù)時間,93,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,3.關(guān)鍵活動有關(guān)的量從ve(0)=0開始向前遞推 ve(j)=Maxve(i)+dut() T，T是所有以第j個頂點為頭的弧的集合從vl(n-1)=ve(n-1)起向后遞推 vl(i)=Minvl(j)-dut() S，S是所有以第i個頂點為尾的弧的集合,94,.,五、關(guān)鍵路徑,第六節(jié)有向無環(huán)圖及其應(yīng)用,4.求關(guān)鍵活動算法從始點v0出發(fā)，令ve0=0，按拓撲有序求vej從終點vn-1出發(fā)，令vln-1=ven-1，按逆拓撲有序求vli根據(jù)各頂點的ve和vl值，求每條弧(活動)ai的最早開始時間eai和最遲開始時間lai如果eai=lai，則ai為關(guān)鍵活動,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()拓撲有序0,1,3,2,4,