深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017圖演示文檔
《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017圖演示文檔》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(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)：元件 邊：連接元件之間的線(xiàn)路 通訊線(xiàn)路圖 頂點(diǎn)：地點(diǎn) 邊：地點(diǎn)間的連線(xià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條邊，稱(chēng)為無(wú)向完全圖,,.,二、無(wú)向圖,6,第一節(jié) 圖的定義與術(shù)語(yǔ),鄰接點(diǎn)：如果(x,y)?E,稱(chēng)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ù)目，記為T(mén)D(x),,.,三、有向圖(Digraph),7,第一節(jié) 圖的定義與術(shù)語(yǔ),用表示從x到y(tǒng)的一條弧(Arc)，且稱(chēng)x為弧尾，y為弧頭， N={V,E}，V={0,1,2,3,4}，E={，，，，， },,.,三、有向圖(完全圖),8,第一節(jié) 圖的定義與術(shù)語(yǔ),如果有向圖有n(n-1)條邊，則稱(chēng)為有向完全圖,,.,三、有向圖,9,第一節(jié) 圖的定義與術(shù)語(yǔ),鄰接：如果?E,稱(chēng)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)有路徑，稱(chēng)x和y是連通的 連通圖：圖中所有頂點(diǎn)都連通,連通圖,非連通圖,,.,七、子圖,13,第一節(jié) 圖的定義與術(shù)語(yǔ),設(shè)有兩個(gè)圖 G＝(V, E) 和 G’＝(V’, E’)。若 V’? V 且 E’?E, 稱(chēng)圖G’是圖G的子圖,,.,八、生成樹(shù),14,第一節(jié) 圖的定義與術(shù)語(yǔ),一個(gè)連通圖的生成樹(shù)是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹(shù)的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 或 ?E A[i][j] = 0 其它,,,.,一、鄰接矩陣,17,第二節(jié) 圖的存儲(chǔ)結(jié)構(gòu),無(wú)向圖的鄰接矩陣為： 有向圖的鄰接矩陣為：,,.,一、鄰接矩陣(性質(zhì)),18,第二節(jié) 圖的存儲(chǔ)結(jié)構(gòu),無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的 其第i行1的個(gè)數(shù)或第i列1的個(gè)數(shù)，等于頂點(diǎn)i的度TD(i) 有向圖的鄰接矩陣可能是不對(duì)稱(chēng)的 其第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)，則稱(chēng)這種帶權(quán)圖為網(wǎng)絡(luò)。 在網(wǎng)絡(luò)中，兩個(gè)頂點(diǎn)如果不鄰接，則被視為距離為無(wú)窮大； wi,j 如果(i,j)?E 或 ?E A[i][j] = ∞ 其它,,,.,一、鄰接矩陣(網(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、畫(huà)出該網(wǎng), 2、寫(xiě)出該網(wǎng)的鄰接矩陣。,,.,一、鄰接矩陣(定義),21,第二節(jié) 圖的存儲(chǔ)結(jié)構(gòu),#define MAXVERTEXNUM 100 //最大頂點(diǎn)數(shù) typedef struct { int VertexNum; //頂點(diǎn)數(shù) char Vertex[MAXVERTEXNUM];//頂點(diǎn)數(shù)據(jù) int AdjMatrix[MAXVERTEXNUM][MAXVERTEXNUM]; // 鄰接矩陣 } Graph; Graph MGraph;,,.,一、鄰接矩陣(創(chuàng)建),22,第二節(jié) 圖的存儲(chǔ)結(jié)構(gòu),#define INFINITY 100 //無(wú)窮大 void CreateGraph(Graph *G) //生成圖 { int i, j; cin >> G->VertexNum; //輸入圖的頂點(diǎn)數(shù) for (i=1; iVertexNum; i++) cin >> G->Vertex[i]; //輸入頂點(diǎn)信息 for (i=1; iVertexNum; i++) { for (j=1; jVertexNum; j++) { cin >> G->AdjMatrix[i][j]; //依次輸入鄰接矩陣 if (G->AdjMatrix[i][j] == -1) G->AdjMatrix[i][j] = 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 VexNode[G->VertexNum+1]; // 申請(qǐng)n個(gè)頭結(jié)點(diǎn) for (i=1; iVertexNum; i++) { cin >> G->AdjList[i].Vertex; // 輸入頂點(diǎn)信息（字符） G->AdjList[i].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)（弧頭）為y q->NextArc = NULL; if ((G->AdjList[j].NextArc==NULL)||(G->AdjList[j].NextArc->Vertex>y)){ q->NextArc = G->AdjList[j].NextArc; // 插入結(jié)點(diǎn) G->AdjList[j].NextArc = q;} else {p = G->AdjList[j].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->AdjList[j].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)始，訪(fǎng)遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次 圖的遍歷主要應(yīng)用于無(wú)向圖,,.,二、深度優(yōu)先搜索(DFS),43,第三節(jié) 圖的遍歷,圖的深度優(yōu)先搜索是樹(shù)的先根遍歷的推廣 圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪(fǎng)問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)。 為了避免重復(fù)訪(fǎng)問(wèn)，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)的輔助數(shù)組 visited [ ],,.,二、深度優(yōu)先搜索(DFS算法),第三節(jié) 圖的遍歷,所有頂點(diǎn)訪(fǎng)問(wèn)標(biāo)志visited[]設(shè)置為FALSE 從某頂點(diǎn)v0開(kāi)始，設(shè)v=v0 1.如果visited[v]=FALSE，則訪(fǎng)問(wèn)該頂點(diǎn)，且設(shè)visited[v]=TRUE 2.如果找到當(dāng)前頂點(diǎn)的一個(gè)新的相鄰頂點(diǎn)w,設(shè)v=w,重復(fù)1 3.否則(說(shuō)明當(dāng)前頂點(diǎn)的所有相鄰頂點(diǎn)都已被訪(fǎng)問(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,V7 DFS次序2:V1,V2,V5,V8,V4,V3,V6,V7,,由于沒(méi)有規(guī)定 訪(fǎng)問(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每向前走一步可能訪(fǎng)問(wèn)一批頂點(diǎn), 不存在往回退的情況 BFS不是一個(gè)遞歸的過(guò)程。,,.,三、廣度優(yōu)先搜索(BFS算法),49,第三節(jié) 圖的遍歷,所有頂點(diǎn)訪(fǎng)問(wèn)標(biāo)志visited[]設(shè)置為FALSE 從某頂點(diǎn)v0開(kāi)始，訪(fǎng)問(wèn)v0，visited[v0]=TRUE，將v0插入隊(duì)列Q 1.如果隊(duì)列Q不空，則從隊(duì)列Q頭上取出一個(gè)頂點(diǎn)v,否則結(jié)束 2.依次找到頂點(diǎn)v的所有相鄰頂點(diǎn)v’，如果visited[v’]=FALSE，訪(fǎng)問(wèn)該頂點(diǎn)v’，visited[v’]=TRUE，將v’插入隊(duì)列Q 3.重復(fù)1,2,,.,三、廣度優(yōu)先搜索(BFS函數(shù)),50,第三節(jié) 圖的遍歷,void BFSTraverse(Graph *G, char FirstVertex) { int i, j; char y, Visited[MAXVERTEXNUM]; VexNode *p; for (i=1; iVertexNum; i++) Visited[i] = ‘F';// 所有結(jié)點(diǎn)對(duì)應(yīng)的訪(fǎng)問(wèn)位 賦初值 InitQueue(GQ); // 清空循環(huán)隊(duì)列 i = GetVexNodeNo(G, FirstVertex); Visited[i] = 'T'; cout AdjList[i].Vertex; EnQueue(GQ, G->AdjList[i].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ú)向圖的鄰接表算法,畫(huà)出相應(yīng)的鄰接表。并寫(xiě)出在該鄰接表上，從頂點(diǎn)4開(kāi)始搜索所得的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。,.,一、無(wú)向圖的連通性,54,第四節(jié) 圖的連通性問(wèn)題,如果無(wú)向圖中，存在不連通的頂點(diǎn)，則該圖稱(chēng)為非連通圖 非連通圖 連通圖,,,.,二、無(wú)向圖的連通分量,55,第四節(jié) 圖的連通性問(wèn)題,非連通圖的極大連通子圖叫做連通分量 若從無(wú)向圖的每一個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行DFS或BFS遍歷，可求得無(wú)向圖的所有連通分量的生成樹(shù)(DFS或BFS生成樹(shù)) 所有連通分量的生成樹(shù)組成了非連通圖的生成森林,,.,二、無(wú)向圖的生成樹(shù),56,第四節(jié) 圖的連通性問(wèn)題,由DFS遍歷，求得連通分量稱(chēng)為DFS生成樹(shù) 由BFS遍歷，求得連通分量稱(chēng)為BFS生成樹(shù),BFS生成樹(shù),DFS生成樹(shù),,.,三、最小生成樹(shù),57,第四節(jié) 圖的連通性問(wèn)題,如果無(wú)向圖中，邊上有權(quán)值，則稱(chēng)該無(wú)向圖為無(wú)向網(wǎng) 如果無(wú)向網(wǎng)中的每個(gè)頂點(diǎn)都相通，稱(chēng)為連通網(wǎng) 最小生成樹(shù)(Minimum Cost Spanning Tree)是代價(jià)最小的連通網(wǎng)的生成樹(shù)，即該生成樹(shù)上的邊的權(quán)值和最小,,.,三、最小生成樹(shù)(準(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)算法生成最小生成樹(shù),59,第四節(jié) 圖的連通性問(wèn)題,假設(shè)N=(V,E)是連通網(wǎng) TE是N上最小生成樹(shù)中邊的集合 1.U={u0}，(u0?V), TE={} 2.在所有u?U,v?V-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的最小生成樹(shù)T，輸出T的各條邊,記錄從頂點(diǎn)集U到V－U的代價(jià)最小的邊的輔助數(shù)組定義 struct { VertexType adjvex; VRType lowcost; } closedge[MAX_VERTEX_NUM]; int i,j,k; k = LocateVex ( G, u ); for ( j=0; j0, vi∈V-U } printf(closedge[k].adjvex, G.vexs[k]); // 輸出生成樹(shù)的邊 closedge[k].lowcost = 0; // 第k頂點(diǎn)并入U(xiǎn)集 for (j=0; j下載提示(請(qǐng)認(rèn)真閱讀)
- 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您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
10 積分
| 下載 |
還剩頁(yè)未讀，繼續(xù)閱讀
- 配套講稿：
如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 演示 文檔
裝配圖網(wǎng)所有資源均是用戶(hù)自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶(hù)書(shū)面授權(quán)，請(qǐng)勿作他用。
鏈接地址：http://m.jqnhouse.com/p-359907.html