深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017圖演示文檔
《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017圖演示文檔》由會員分享，可在線閱讀，更多相關(guān)《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017圖演示文檔（96頁珍藏版）》請在裝配圖網(wǎng)上搜索。
.,第七章 圖,,,數(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 且 E’?E, 稱圖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 或 ?E A[i][j] = 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 或 ?E A[i][j] = ∞ 其它,,,.,一、鄰接矩陣(網(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 Vertex[MAXVERTEXNUM];//頂點數(shù)據(jù) int AdjMatrix[MAXVERTEXNUM][MAXVERTEXNUM]; // 鄰接矩陣 } Graph; Graph MGraph;,,.,一、鄰接矩陣(創(chuàng)建),22,第二節(jié) 圖的存儲結(jié)構(gòu),#define INFINITY 100 //無窮大 void CreateGraph(Graph *G) //生成圖 { int i, j; cin >> G->VertexNum; //輸入圖的頂點數(shù) for (i=1; iVertexNum; i++) cin >> G->Vertex[i]; //輸入頂點信息 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é) 圖的存儲結(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 VexNode[G->VertexNum+1]; // 申請n個頭結(jié)點 for (i=1; iVertexNum; i++) { cin >> G->AdjList[i].Vertex; // 輸入頂點信息（字符） G->AdjList[i].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; // 邊的另一個頂點（弧頭）為y q->NextArc = NULL; if ((G->AdjList[j].NextArc==NULL)||(G->AdjList[j].NextArc->Vertex>y)){ q->NextArc = G->AdjList[j].NextArc; // 插入結(jié)點 G->AdjList[j].NextArc = q;} else {p = G->AdjList[j].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->AdjList[j].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=v0 1.如果visited[v]=FALSE，則訪問該頂點，且設(shè)visited[v]=TRUE 2.如果找到當(dāng)前頂點的一個新的相鄰頂點w,設(shè)v=w,重復(fù)1 3.否則(說明當(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,V7 DFS次序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，visited[v0]=TRUE，將v0插入隊列Q 1.如果隊列Q不空，則從隊列Q頭上取出一個頂點v,否則結(jié)束 2.依次找到頂點v的所有相鄰頂點v’，如果visited[v’]=FALSE，訪問該頂點v’，visited[v’]=TRUE，將v’插入隊列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é)點對應(yīng)的訪問位 賦初值 InitQueue(GQ); // 清空循環(huán)隊列 i = GetVexNodeNo(G, FirstVertex); Visited[i] = 'T'; cout AdjList[i].Vertex; EnQueue(GQ, G->AdjList[i].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ā)進(jìn)行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)值的總和達(dá)到最小。,,.,四、普里姆(Prim)算法生成最小生成樹,59,第四節(jié) 圖的連通性問題,假設(shè)N=(V,E)是連通網(wǎng) TE是N上最小生成樹中邊的集合 1.U={u0}，(u0?V), TE={} 2.在所有u?U,v?V-U的邊(u,v)?E中找一條代價最小的邊(u,v0)并入集合TE，同時v0并入U 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個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，輸出T的各條邊,記錄從頂點集U到V－U的代價最小的邊的輔助數(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]); // 輸出生成樹的邊 closedge[k].lowcost = 0; // 第k頂點并入U集 for (j=0; j下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
10 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 深圳大學(xué) 數(shù)據(jù)結(jié)構(gòu) 2017 演示 文檔
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://kudomayuko.com/p-359907.html