深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017圖演示文檔
《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017圖演示文檔》由會(huì)員分享,可在線閱讀,更多相關(guān)《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017圖演示文檔(96頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
.,第七章圖,數(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ù)對(duì)象是頂點(diǎn)的有窮非空集合 E是頂點(diǎn)之間關(guān)系的有窮集合,包括 E1 = (x, y) | x, y V 邊的集合 或 E2 = | x, y V 弧的集合,第一節(jié)圖的定義與術(shù)語(yǔ),.,第一節(jié)圖的定義與術(shù)語(yǔ),交通圖(公路、鐵路) 頂點(diǎn):地點(diǎn) 邊:連接地點(diǎn)的公路交通圖中有單行道雙行道,分別用有向邊、無(wú)向邊表示;電路圖 頂點(diǎn):元件 邊:連接元件之間的線路通訊線路圖 頂點(diǎn):地點(diǎn) 邊:地點(diǎn)間的連線,.,二、無(wú)向圖(Undigraph),4,第一節(jié)圖的定義與術(shù)語(yǔ),用(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),.,二、無(wú)向圖(完全圖),5,第一節(jié)圖的定義與術(shù)語(yǔ),如果無(wú)向圖有n(n-1)/2條邊,稱為無(wú)向完全圖,.,二、無(wú)向圖,6,第一節(jié)圖的定義與術(shù)語(yǔ),鄰接點(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ù)語(yǔ),用表示從x到y(tǒng)的一條弧(Arc),且稱x為弧尾,y為弧頭,N=V,E,V=0,1,2,3,4,E=, ,.,三、有向圖(完全圖),8,第一節(jié)圖的定義與術(shù)語(yǔ),如果有向圖有n(n-1)條邊,則稱為有向完全圖,.,三、有向圖,9,第一節(jié)圖的定義與術(shù)語(yǔ),鄰接:如果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ù)語(yǔ),路徑:是一個(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ù)語(yǔ),回路或環(huán):路徑的開(kāi)始頂點(diǎn)與最后一個(gè)頂點(diǎn)相同,即路徑中(x, vi1, vi2, vin, y),x=y簡(jiǎn)單路徑:路徑的頂點(diǎn)序列中,頂點(diǎn)不重復(fù)出現(xiàn),1到1構(gòu)成環(huán)(1,0,4,3,1),1到3是簡(jiǎn)單路徑(1,0,4,3),.,六、連通,12,第一節(jié)圖的定義與術(shù)語(yǔ),連通:如果頂點(diǎn)x到y(tǒng)有路徑,稱x和y是連通的連通圖:圖中所有頂點(diǎn)都連通,連通圖,非連通圖,.,七、子圖,13,第一節(jié)圖的定義與術(shù)語(yǔ),設(shè)有兩個(gè)圖 G(V, E) 和 G(V, E)。若 V V 且 EE, 稱圖G是圖G的子圖,.,八、生成樹,14,第一節(jié)圖的定義與術(shù)語(yǔ),一個(gè)連通圖的生成樹是一個(gè)極小連通子圖,它含有圖中全部n個(gè)頂點(diǎn),但只有足以構(gòu)成一棵樹的n-1條邊,.,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),圖的鄰接矩陣存儲(chǔ)表示法圖的鄰接表表示法圖的逆鄰接表表示法圖的十字鏈表表示法圖的鄰接多重表表示法,.,一、鄰接矩陣(Adjacency Matrix),16,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),鄰接矩陣:記錄圖中各頂點(diǎn)之間關(guān)系的二維數(shù)組。對(duì)于不帶權(quán)的圖,以1表示兩頂點(diǎn)存在邊(或弧)(相鄰接),以0表示兩頂點(diǎn)不鄰接,即 1 如果(i,j)E 或 EAij = 0 其它,.,一、鄰接矩陣,17,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),無(wú)向圖的鄰接矩陣為:有向圖的鄰接矩陣為:,.,一、鄰接矩陣(性質(zhì)),18,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),無(wú)向圖的鄰接矩陣是對(duì)稱的其第i行1的個(gè)數(shù)或第i列1的個(gè)數(shù),等于頂點(diǎn)i的度TD(i)有向圖的鄰接矩陣可能是不對(duì)稱的其第i行1的個(gè)數(shù)等于頂點(diǎn)i的出度OD(i),第j列1的個(gè)數(shù)等于頂點(diǎn)j的入度ID(j),.,一、鄰接矩陣(網(wǎng)絡(luò)),19,第二節(jié)圖的存儲(chǔ)結(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)如果不鄰接,則被視為距離為無(wú)窮大; wi,j 如果(i,j)E 或 EAij = 其它,.,一、鄰接矩陣(網(wǎng)絡(luò)),20,第二節(jié)圖的存儲(chǔ)結(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é)圖的存儲(chǔ)結(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é)圖的存儲(chǔ)結(jié)構(gòu),#define INFINITY100/無(wú)窮大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é)圖的存儲(chǔ)結(jié)構(gòu),鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在鄰接表中,每個(gè)頂點(diǎn)設(shè)置一個(gè)單鏈表,其每個(gè)結(jié)點(diǎn)都是依附于該頂點(diǎn)的邊(或以該頂點(diǎn)為尾的弧),.,二、鄰接表(結(jié)點(diǎn)結(jié)構(gòu)),24,第二節(jié)圖的存儲(chǔ)結(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é)圖的存儲(chǔ)結(jié)構(gòu),二、鄰接表(結(jié)點(diǎn)結(jié)構(gòu)),.,二、鄰接表(無(wú)向圖),26,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),.,二、鄰接表(有向圖),27,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),.,二、鄰接表(網(wǎng)絡(luò)),28,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),.,二、鄰接表(定義),29,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),typedef struct / 定義圖(采用鄰接鏈表)int VertexNum;/ 頂點(diǎn)數(shù)VexNode *AdjList;/ 鄰接表頭指針 Graph;Graph MGraph;,.,二、鄰接表(創(chuàng)建),30,第二節(jié)圖的存儲(chǔ)結(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; / 申請(qǐng)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)(無(wú)向圖),.,二、鄰接表(創(chuàng)建插入結(jié)點(diǎn)),31,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),void InsertLinkList(Graph *G, char x, char y)int j;VexNode *p, *q;j = GetVexNodeNo(G, x); / 找到頂點(diǎn)x對(duì)應(yīng)的單鏈表頭結(jié)點(diǎn)q = new VexNode;/ 申請(qǐng)一個(gè)新結(jié)點(diǎn)q-Vertex = y;/ 邊的另一個(gè)頂點(diǎn)(弧頭)為yq-NextArc = NULL;if (G-AdjListj.NextArc=NULL)|(G-AdjListj.NextArc-Vertexy)q-NextArc = G-AdjListj.NextArc; / 插入結(jié)點(diǎn)G-AdjListj.NextArc = q;else p = G-AdjListj.NextArc;while(p-NextArc),.,二、鄰接表(創(chuàng)建頂點(diǎn)對(duì)應(yīng)的序號(hào)),32,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),int GetVexNodeNo(Graph *G, char c) / 找到字符對(duì)應(yīng)的單鏈表序號(hào) int j; for (j=1; jVertexNum; j+) if (G-AdjListj.Vertex = c) break; return(j);,.,二、鄰接表(性質(zhì)),33,第二節(jié)圖的存儲(chǔ)結(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é)圖的存儲(chǔ)結(jié)構(gòu),逆鄰接表中,弧的箭頭向內(nèi)(入弧),.,三、十字鏈表(Orthogonal List),35,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),十字鏈表是有向圖的另一種存儲(chǔ)結(jié)構(gòu)十字鏈表是將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)的一種存儲(chǔ)結(jié)構(gòu),.,三、十字鏈表(結(jié)點(diǎn)結(jié)構(gòu)),36,第二節(jié)圖的存儲(chǔ)結(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é)圖的存儲(chǔ)結(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é)圖的存儲(chǔ)結(jié)構(gòu),.,四、鄰接多重表(Adjacency Multilist),39,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),鄰接多重表是無(wú)向圖的另一種存儲(chǔ)結(jié)構(gòu)在無(wú)向圖中,一條邊要用2個(gè)結(jié)點(diǎn)表示(分別從2個(gè)頂點(diǎn)的角度看)在鄰接多重表中,一條邊只用一個(gè)結(jié)點(diǎn)表示將所有具有某頂點(diǎn)的結(jié)點(diǎn),全部用鏈連結(jié)起來(lái),鏈所在的域?yàn)樵擁旤c(diǎn)對(duì)應(yīng)的指針域,.,四、鄰接多重表(結(jié)點(diǎn)結(jié)構(gòu)),40,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),邊的結(jié)點(diǎn)結(jié)構(gòu) mark; / 標(biāo)記域,如指示該邊是否被搜索過(guò) ivex,jvex;/ 該邊所依附的兩個(gè)頂點(diǎn)的位置 ilink;/ 指向下一條依附于ivex的邊 jlink;/ 指向下一條依附于jvex的邊 info; / 該邊相關(guān)信息的指針或權(quán)值,.,四、鄰接多重表(舉例),41,第二節(jié)圖的存儲(chǔ)結(jié)構(gòu),.,一、圖的遍歷,42,第三節(jié)圖的遍歷,從圖的某一頂點(diǎn)開(kāi)始,訪遍圖中其余頂點(diǎn),且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次圖的遍歷主要應(yīng)用于無(wú)向圖,.,二、深度優(yōu)先搜索(DFS),43,第三節(jié)圖的遍歷,圖的深度優(yōu)先搜索是樹的先根遍歷的推廣圖中可能存在回路,且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通,在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。為了避免重復(fù)訪問(wèn),可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問(wèn)過(guò)的輔助數(shù)組 visited ,.,二、深度優(yōu)先搜索(DFS算法),第三節(jié)圖的遍歷,所有頂點(diǎn)訪問(wèn)標(biāo)志visited設(shè)置為FALSE從某頂點(diǎn)v0開(kāi)始,設(shè)v=v01.如果visitedv=FALSE,則訪問(wèn)該頂點(diǎn),且設(shè)visitedv=TRUE2.如果找到當(dāng)前頂點(diǎn)的一個(gè)新的相鄰頂點(diǎn)w,設(shè)v=w,重復(fù)13.否則(說(shuō)明當(dāng)前頂點(diǎn)的所有相鄰頂點(diǎn)都已被訪問(wèn)過(guò),或者當(dāng)前頂點(diǎn)沒(méi)有相鄰頂點(diǎn)),如果當(dāng)前頂點(diǎn)是v0,退出;否則返回上一級(jí)頂點(diǎn),重復(fù)2,.,二、深度優(yōu)先搜索(舉例),45,第三節(jié)圖的遍歷,采用以下鏈表存儲(chǔ)結(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,由于沒(méi)有規(guī)定訪問(wèn)鄰接點(diǎn)的順序,深度優(yōu)先序列不唯一,.,第三節(jié)圖的遍歷,當(dāng)采用鄰接表存儲(chǔ)結(jié)構(gòu)并且存儲(chǔ)結(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每向前走一步可能訪問(wèn)一批頂點(diǎn), 不存在往回退的情況BFS不是一個(gè)遞歸的過(guò)程。,.,三、廣度優(yōu)先搜索(BFS算法),49,第三節(jié)圖的遍歷,所有頂點(diǎn)訪問(wèn)標(biāo)志visited設(shè)置為FALSE從某頂點(diǎn)v0開(kāi)始,訪問(wèn)v0,visitedv0=TRUE,將v0插入隊(duì)列Q1.如果隊(duì)列Q不空,則從隊(duì)列Q頭上取出一個(gè)頂點(diǎn)v,否則結(jié)束2.依次找到頂點(diǎn)v的所有相鄰頂點(diǎn)v,如果visitedv=FALSE,訪問(wèn)該頂點(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)對(duì)應(yīng)的訪問(wèn)位 賦初值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ì)是對(duì)每個(gè)頂點(diǎn)查找鄰接點(diǎn)的過(guò)程,取決于存儲(chǔ)結(jié)構(gòu)。當(dāng)圖有e條邊,其時(shí)間復(fù)雜度為O(e),圖的每個(gè)頂點(diǎn)至多調(diào)用一次DFS函數(shù)(遞歸過(guò)程)。 總時(shí)間復(fù)雜度為O(n+e) 。 BFS遍歷: 與DFS遍歷唯一區(qū)別是鄰接點(diǎn)搜索次序不同. 總時(shí)間復(fù)雜度為O(n+e) 。,第三節(jié)圖的遍歷,.,練 習(xí),例按順序輸入頂點(diǎn)對(duì):(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5), 根據(jù)建立無(wú)向圖的鄰接表算法,畫出相應(yīng)的鄰接表。并寫出在該鄰接表上,從頂點(diǎn)4開(kāi)始搜索所得的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。,.,一、無(wú)向圖的連通性,54,第四節(jié)圖的連通性問(wèn)題,如果無(wú)向圖中,存在不連通的頂點(diǎn),則該圖稱為非連通圖 非連通圖 連通圖,.,二、無(wú)向圖的連通分量,55,第四節(jié)圖的連通性問(wèn)題,非連通圖的極大連通子圖叫做連通分量若從無(wú)向圖的每一個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行DFS或BFS遍歷,可求得無(wú)向圖的所有連通分量的生成樹(DFS或BFS生成樹)所有連通分量的生成樹組成了非連通圖的生成森林,.,二、無(wú)向圖的生成樹,56,第四節(jié)圖的連通性問(wèn)題,由DFS遍歷,求得連通分量稱為DFS生成樹由BFS遍歷,求得連通分量稱為BFS生成樹,BFS生成樹,DFS生成樹,.,三、最小生成樹,57,第四節(jié)圖的連通性問(wèn)題,如果無(wú)向圖中,邊上有權(quán)值,則稱該無(wú)向圖為無(wú)向網(wǎng)如果無(wú)向網(wǎng)中的每個(gè)頂點(diǎn)都相通,稱為連通網(wǎng)最小生成樹(Minimum Cost Spanning Tree)是代價(jià)最小的連通網(wǎng)的生成樹,即該生成樹上的邊的權(quán)值和最小,.,三、最小生成樹(準(zhǔn)則),58,第四節(jié)圖的連通性問(wèn)題,必須使用且僅使用連通網(wǎng)中的n-1條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn);不能使用產(chǎn)生回路的邊;各邊上的權(quán)值的總和達(dá)到最小。,.,四、普里姆(Prim)算法生成最小生成樹,59,第四節(jié)圖的連通性問(wèn)題,假設(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é)圖的連通性問(wèn)題,原圖 (a) (b),(c) (d) (e) (f),.,P174頁(yè),圖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; jG.vexnum; +j) if (G.arcskj.adj Vertexi = StartVexChar) StartVex = i; break;for (i=1; iVertexNum; i+) Pathi0 = 0; / 順序表的0位置,存放順序表(路徑)的長(zhǎng)度 Desti = INFINITY;/ 所有頂點(diǎn)到開(kāi)始頂點(diǎn)之間的距離初值設(shè)為無(wú)窮大 if (G-AdjMatrixStartVexi AdjMatrixStartVexi; Pathi1 = G-VertexStartVex; Pathi2 = G-Vertexi; Pathi0 = 2; Finali = F;,76,.,三、Dijkstra算法代碼,第五節(jié)最短路徑,DestStartVex = 0; / 初始化,開(kāi)始頂點(diǎn)屬于S集(已處理過(guò)的結(jié)點(diǎn))FinalStartVex = T;for (i=1; iVertexNum; i+) MinDest = INFINITY; for (j=1; jVertexNum; j+) / 找未處理頂點(diǎn)中到開(kāi)始頂點(diǎn)最近的頂點(diǎn) if (Finalj = F) if (Destj VertexNum; j+) / 更新當(dāng)前最短路徑及距離 if(Finalj=F) ,77,.,一、有向無(wú)環(huán)圖(DAG),第六節(jié)有向無(wú)環(huán)圖及其應(yīng)用,有向無(wú)環(huán)圖(DAG:Directed Acycline Graph)是圖中無(wú)環(huán)的有向圖,DAG,非DAG,78,.,一、有向無(wú)環(huán)圖(DAG),第六節(jié)有向無(wú)環(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é)有向無(wú)環(huán)圖及其應(yīng)用,1.偏序若集合X上的關(guān)系R是:.自反的:x R x.反對(duì)稱的:x R y = y R x.傳遞的:xRy & yRz = xRz 則稱R是集合X上的偏序關(guān)系,.,二、拓?fù)渑判?第六節(jié)有向無(wú)環(huán)圖及其應(yīng)用,2.全序設(shè)關(guān)系R是集合X上的偏序,如果對(duì)每個(gè)x,yX,必有xRy或者yRx,則稱R是X上的全序關(guān)系偏序指集合中僅有部分成員之間可比較全序指集合中全體成員之間均可比較,81,.,二、拓?fù)渑判?第六節(jié)有向無(wú)環(huán)圖及其應(yīng)用,3.拓?fù)溆行蛴覉D是一個(gè)偏序關(guān)系,因?yàn)?,3沒(méi)有先后關(guān)系如果人為地增加1,3先后關(guān)系,如1先于3,則右圖變?yōu)槿颍?稱為拓?fù)溆行?.,二、拓?fù)渑判?第六節(jié)有向無(wú)環(huán)圖及其應(yīng)用,4.拓?fù)渑判蛴善蚨x得到的拓?fù)溆行虻牟僮鞣Q拓?fù)渑判蛩惴ǎ?在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之.從圖中刪除該頂點(diǎn)和所有以它為尾的弧 重復(fù)兩步,直到所有頂點(diǎn)輸出為止,83,.,第六節(jié)有向無(wú)環(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 (countG.vexnum) return (ERROR);else return (OK);/end of ToptlogicalSort() function,.,二、拓?fù)渑判?舉例),第六節(jié)有向無(wú)環(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é)有向無(wú)環(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é)有向無(wú)環(huán)圖及其應(yīng)用,課程代號(hào) 課程名稱 先修課程C1 高等數(shù)學(xué)C2 程序設(shè)計(jì)基礎(chǔ)C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2C5 高級(jí)語(yǔ)言程序設(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é)有向無(wú)環(huán)圖及其應(yīng)用,如果用有向圖的頂點(diǎn)表示事件,用弧表示活動(dòng),則稱該有向圖為邊表示活動(dòng)的網(wǎng)AOE(Activity On Edge)AOE同樣是DAGAOE包括估算工程的完成時(shí)間,.,五、關(guān)鍵路徑,第六節(jié)有向無(wú)環(huán)圖及其應(yīng)用,求工程的完成時(shí)間是AOE的一個(gè)應(yīng)用在工程問(wèn)題中,需要研究的問(wèn)題有:.完成整個(gè)工程至少需要多少時(shí)間?.哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵?,89,.,五、關(guān)鍵路徑,第六節(jié)有向無(wú)環(huán)圖及其應(yīng)用,1.關(guān)鍵路徑工程問(wèn)題的AOE網(wǎng)中,從工程開(kāi)始(頂點(diǎn))到工程結(jié)束(頂點(diǎn))之間路徑長(zhǎng)度最長(zhǎng)的路徑叫關(guān)鍵路徑提前完成關(guān)鍵路徑上的活動(dòng),工程進(jìn)度會(huì)加快提前完成非關(guān)鍵路徑上的活動(dòng),對(duì)工程無(wú)幫助,90,.,五、關(guān)鍵路徑,第六節(jié)有向無(wú)環(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é)有向無(wú)環(huán)圖及其應(yīng)用,3.關(guān)鍵活動(dòng)有關(guān)的量e(i):活動(dòng)ai最早開(kāi)始時(shí)間l(i):活動(dòng)ai最遲開(kāi)始時(shí)間l(i)-e(i):活動(dòng)ai開(kāi)始時(shí)間余量如果l(i)=e(i),則稱活動(dòng)ai為關(guān)鍵活動(dòng),92,.,五、關(guān)鍵路徑,第六節(jié)有向無(wú)環(huán)圖及其應(yīng)用,3.關(guān)鍵活動(dòng)有關(guān)的量ve(j):事件vj最早開(kāi)始時(shí)間vl(j):事件vj最遲開(kāi)始時(shí)間e(i)=ve(j)l(j)=vl(k)-dut() dut()為活動(dòng)ai的持續(xù)時(shí)間,93,.,五、關(guān)鍵路徑,第六節(jié)有向無(wú)環(huán)圖及其應(yīng)用,3.關(guān)鍵活動(dòng)有關(guān)的量從ve(0)=0開(kāi)始向前遞推 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é)有向無(wú)環(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的最早開(kāi)始時(shí)間eai和最遲開(kāi)始時(shí)間lai如果eai=lai,則ai為關(guān)鍵活動(dòng),95,.,五、關(guān)鍵路徑(舉例),第六節(jié)有向無(wú)環(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,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
10 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 深圳大學(xué) 數(shù)據(jù)結(jié)構(gòu) 2017 演示 文檔
鏈接地址:http://ioszen.com/p-359907.html