清華名師數(shù)據(jù)結(jié)構(gòu)考研輔導(dǎo)課件附帶考試大綱第七章圖

1、圖2022/7/22考研輔導(dǎo)四、圖圖 （一） 圖的概念 （二） 圖的存儲(chǔ)及基本操作 1. 鄰接矩陣法 2. 鄰接表法 （三） 圖的遍歷 1. 深度優(yōu)先搜索 2. 廣度優(yōu)先搜索2022/7/22考研輔導(dǎo)四、圖（四） 圖的基本應(yīng)用及其復(fù)雜度分析 1. 最小（代價(jià)）生成樹 2. 最短路徑 3. 拓?fù)渑判?4. 關(guān)鍵路徑2022/7/22考研輔導(dǎo)圖的概念A(yù)DT graph數(shù)據(jù)對(duì)象V： V是具有相同特性的數(shù)據(jù)元素的集合，稱頂點(diǎn)集數(shù)據(jù)關(guān)系R： R=VR VR| v,wV 且 P(v,w) 表示從 v 到 w 的弧 謂詞 P(v,w)定義了弧 的意義或信息基本操作P： 結(jié)構(gòu)的建立和銷毀 對(duì)頂點(diǎn)的訪問操作 插

2、入或刪除頂點(diǎn) 插入和刪除弧 對(duì)鄰接點(diǎn)的操作 遍歷ADT graph2022/7/22考研輔導(dǎo)圖的概念一組概念：有向圖，弧，弧頭，弧尾，子圖/無向圖，邊/網(wǎng)，有向網(wǎng)，無向網(wǎng)完全圖，稀疏圖 (邊或弧的個(gè)數(shù)enlogn)，稠密圖鄰接點(diǎn)(鄰接到，鄰接自/關(guān)聯(lián))/度、入度、出度路徑，路徑長度，簡單路徑，簡單回路連通圖、連通分量/強(qiáng)連通圖、強(qiáng)連通分量生成樹(連通圖)/生成森林(非連通圖)returnABECDACDFEBABECD65473152022/7/22考研輔導(dǎo)圖的鄰接矩陣存儲(chǔ)及操作鄰接矩陣用兩個(gè)數(shù)組分別存儲(chǔ)：數(shù)據(jù)元素（頂點(diǎn)）數(shù)據(jù)元素之間的關(guān)系（邊或弧）的信息。存儲(chǔ)邊信息的數(shù)組用鄰接矩陣表示，鄰接

3、矩陣的元素定義為：Aij=0 (Vi ,Vj)VR1 (Vi ,Vj)VR2022/7/22考研輔導(dǎo)圖的鄰接矩陣存儲(chǔ)及操作無向圖的鄰接矩陣一定是對(duì)稱矩陣。010010100011000101001001110000011100ACDFEB2022/7/22考研輔導(dǎo)圖的鄰接矩陣存儲(chǔ)及操作有向圖的鄰接矩陣不一定是非對(duì)稱矩陣。ABECD01001001000001011000001002022/7/22考研輔導(dǎo)圖的鄰接矩陣存儲(chǔ)及操作網(wǎng)的鄰接矩陣可定義為：ABECD6547315065010547030Aij=Wi,j 若(Vi ,Vj)或 VR 反之2022/7/22考研輔導(dǎo)圖的鄰接矩陣存儲(chǔ)及操作圖

4、的數(shù)組（鄰接矩陣）存儲(chǔ)表示#define INFINITY INF_MAX /最大值#define MAX_VERTEX_NUM 20 /最大頂點(diǎn)個(gè)數(shù)typedef enumDG,DN,UDG,UDN GraphKind; / 有向圖,有向網(wǎng),無向圖,無向網(wǎng)/定義弧typedef struct ArcCell VRType adj; /表示頂點(diǎn)關(guān)系的值的類型.無權(quán)圖:adj為1或0; 帶權(quán)圖:adj為權(quán)值,VRType為權(quán)值類型 InfoType *info; / 該弧相關(guān)信息的指針ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; / 定義鄰接矩陣

5、AdjMatrix為ArcCell類型的二維數(shù)組2022/7/22考研輔導(dǎo)圖的鄰接矩陣存儲(chǔ)及操作圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示/定義圖typedef struct VertexType vexsMAX_VERTEX_NUM; /頂點(diǎn)向量,存儲(chǔ)頂點(diǎn) AdjMatrix arcs; /鄰接矩陣,存儲(chǔ)邊或弧。AdjMatrix為二維數(shù)組類型 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) GraphKind kind; /圖的種類標(biāo)志MGraph2022/7/22考研輔導(dǎo)圖的鄰接矩陣存儲(chǔ)及操作圖的鄰接矩陣存儲(chǔ)表示法的操作：構(gòu)造圖 算法7.1Status CreateGraph( MGra

6、ph &G ) scanf(&G.kind); /獲取圖的種類標(biāo)志 switch(G.kind) case DG:return CreateDG(G); /構(gòu)造有向圖G case DN:return CreateDN(G); /構(gòu)造有向網(wǎng)G case UDG:return CreateUDG(G); /構(gòu)造無向圖G case UDN:return CreateUDN(G); /構(gòu)造無向網(wǎng)G default:return ERROR; 2022/7/22考研輔導(dǎo)圖的鄰接矩陣存儲(chǔ)及操作圖的鄰接矩陣存儲(chǔ)表示法的操作：構(gòu)造無向網(wǎng) 算法7.2Status CreateUDN(MGraph &G) sca

7、nf(&G.vexnum,&G.arcnum,&IncInfo); /讀取圖的頂點(diǎn)數(shù),邊數(shù),弧信息IncInfo為0則各弧不含其他信息 for(i=0;iG.vexnum;+i) scanf(&G.vexsi); /構(gòu)造頂點(diǎn)向量 for(i=0;iG.vexnum;+i) /初始化鄰接矩陣 for(j=0;jG.vexnum;+j) G.arcsij=INFINITY,NULL; /adj,infoadj為2022/7/22考研輔導(dǎo)圖的鄰接矩陣存儲(chǔ)及操作 for(k=0;kG.vexnum;+k) /構(gòu)造鄰接矩陣 scanf(&v1,&v2,&w); /輸入一條邊依附的頂點(diǎn)及權(quán)值 i=Loca

8、teVex(G,v1); j=LocateVex(G,v2); /確定v1和v2在G中位置 G.arcsij.adj=w; /弧的權(quán)值 if(IncInfo) Input(*G.); /若該弧含有相關(guān)信息，則輸入它 G.arcsji=G.arcsij；/置的對(duì)稱弧 return OK; return2022/7/22考研輔導(dǎo)圖的鄰接表存儲(chǔ)鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接表中，為圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表：第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊(對(duì)有向圖是以vi頂點(diǎn)為尾的弧)/定義弧typedef struct ArcNodeint adjvex; /該弧所指向的頂

9、點(diǎn)的位置 struct ArcNode *nextarc; /指向下一條弧的指針 InfoType *info; /該弧相關(guān)信息的指針ArcNode;infoadjvexnextarc2022/7/22考研輔導(dǎo)圖的鄰接表存儲(chǔ)/定義頂點(diǎn)typedef struct VNode VertexType data; /頂點(diǎn)信息 ArcNode *firstarc; /指向第一條依附該頂點(diǎn)的弧 VNode, AdjListMAX_VERTEX_NUM;/定義圖typedef struct AdjList vertices; /頂點(diǎn)向量 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) int

10、 kind; /圖的種類標(biāo)志 ALGraph;datafirstarc2022/7/22考研輔導(dǎo)圖的鄰接表存儲(chǔ)無向圖的鄰接表14ACDFEBABCDEF0123453525015041232022/7/22考研輔導(dǎo)圖的鄰接表存儲(chǔ)有向圖的鄰接表14ABCDE01234201ABECD23return2022/7/22考研輔導(dǎo)圖的遍歷深度優(yōu)先搜索 從圖中某個(gè)頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn); 然后依次從V0的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到； 若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到

11、為止。如圖：設(shè)各頂點(diǎn)在數(shù)組中存儲(chǔ)順序?yàn)椋?v1,v2 ,v3 ,v4 ,v5 ,v6 ,v7 ,v8則該圖深度優(yōu)先搜索的序列為：v1v2 v4 v8 v5 v3 v6 v7V1V2V6V3V4V5V7v82022/7/22考研輔導(dǎo)圖的遍歷ABCDEFG訪問序列：ABCEDFG231414231ABCDEF012345G6652022/7/22考研輔導(dǎo)圖的遍歷如何判別V的鄰接點(diǎn)是否被訪問？解決方法：為每個(gè)頂點(diǎn)設(shè)立一個(gè)訪問標(biāo)志:visitedw，其初值為false，一旦某個(gè)頂點(diǎn)被訪問，將該值置為true。/從第v個(gè)頂點(diǎn)出發(fā)，深度優(yōu)先遍歷圖G 算法 7.5void DFS(Graph G,int v

12、) visitedv=TRUE; VisitFunc(v); /訪問第v個(gè)頂點(diǎn) for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); /對(duì)v的尚未訪問的鄰接頂點(diǎn)w，遞歸調(diào)用DFS 2022/7/22考研輔導(dǎo)圖的遍歷/深度優(yōu)先遍歷圖G 算法 7.4/VisitFunc,visited為全局變量void DFSTraverse(Graph G,Status(*Visit)(int v) VisitFunc=Visit; for(v=0;vG.vexnum;+v) visitedv=FALSE; /訪問標(biāo)志數(shù)組初

13、始化 for(v=0;vG.vexnum;+v) if(!visitedv) DFS(G,v); /對(duì)尚未訪問的頂點(diǎn)調(diào)用DFS2022/7/22考研輔導(dǎo)圖的遍歷廣度優(yōu)先搜索 從圖中某個(gè)頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn); 然后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到; 若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。如圖：設(shè)各頂點(diǎn)在數(shù)組中存儲(chǔ)順序?yàn)椋?v1,v2 ,v3 ,v4 ,v5 ,v6 ,v7 ,v8則該圖廣度優(yōu)先搜索的序列為：v1v2

14、v3 v4 v5 v6 v7 v8V1V2V6V3V4V5V7v82022/7/22考研輔導(dǎo)圖的遍歷ABCDEFG訪問序列：ABCDEFG231414231ABCDEF012345G6652022/7/22考研輔導(dǎo)/廣度優(yōu)先非遞歸遍歷圖G，使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited 算法7.6void BFSTraverse(Graph G,Status(*Visit)(int v) for(v=0;vG.vexnum;+v) visitedv=FALSE; /初始化訪問標(biāo)志 InitQueue(Q); /置空的輔助隊(duì)列Q,P59隊(duì)列定義 for(v=0;v=0;w=NextAdjVex(G,

15、u,w) if(!visitedw) /W為u的尚未訪問的鄰接頂點(diǎn) visitedw=TRUE;Visit(w); EnQueue(Q,w); /訪問的頂點(diǎn)w入隊(duì)列 return2022/7/22考研輔導(dǎo)最小生成樹生成樹一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹是一個(gè)極小連通子圖，它包含圖中的全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。最小生成樹一個(gè)有n個(gè)頂點(diǎn)，e條邊的連通網(wǎng)的最小生成樹是： 它包含圖中的全部頂點(diǎn); 它包含圖中的n-1條邊，且n-1條邊的“權(quán)值之和”為最小; 它無回路。生成最小生成樹的方法方法一：普里姆算法 方法二：克魯斯卡爾算法 2022/7/22考研輔導(dǎo)最小生成樹普里姆算法基本思想（加

16、頂點(diǎn)法） 設(shè)生成樹的頂點(diǎn)集合為U，邊集合為TE，連通網(wǎng)的頂點(diǎn)集合為V; 則未加入生成樹的頂點(diǎn)集合為V-U。取連通網(wǎng)中任意一個(gè)頂點(diǎn)u作為生成樹的根;U=u然后往生成樹上添加新的頂點(diǎn)w，該頂點(diǎn)滿足： wV-U UV-U存在多條邊，權(quán)值最小的邊在V-U中對(duì)應(yīng)的頂點(diǎn)即為頂點(diǎn)w;同時(shí)將對(duì)應(yīng)邊加入TE；重復(fù)直至U=V。在尋找UV-U的權(quán)值最小的邊時(shí)，需設(shè)置一個(gè)輔助數(shù)組closedge：對(duì)VU中的某頂點(diǎn)Vx，可能U中有多個(gè)頂點(diǎn)與Vx關(guān)聯(lián)，在這些邊中取權(quán)最小的邊：故數(shù)組元素closedgei需存儲(chǔ)兩個(gè)信息，最小權(quán)、與該最小權(quán)邊相連的U中某頂點(diǎn)。在數(shù)組closedge中查找”最小權(quán)”最小的元素，便可找到頂點(diǎn)w。

17、2022/7/22考研輔導(dǎo)6155563426V1V2V6V3V5V4V1V2V3V4V6V5012354V10V16V11V15V1V1V1-：closedge 變化過程：V10V35V10V15V34V36V1，V3-：V10V35V10V42V30V36V1，V3，V6-： 0000002022/7/22考研輔導(dǎo)/用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G(鄰接矩陣表示法:P161)的最小生成樹 算法7.9void MiniSpanTree_P(MGraph G,VertexType u) k=LocateVex(G,u); /確定第一個(gè)頂點(diǎn)u的存儲(chǔ)位置 for(j=0;jG.vexnum;+j)

18、 /closedge數(shù)組初始化:從u頂點(diǎn)發(fā)向各頂點(diǎn) if(j!=k) closedgej=u,G.arcskj.adj;/每個(gè)頂點(diǎn)的關(guān)聯(lián)頂點(diǎn)為u closedgek.lowcost=0; /初始,U=u.每并入一個(gè)頂點(diǎn),將權(quán)置0 for(i=0;iG.vexnum;+i) /大循環(huán)：將剩余所有頂點(diǎn)依次加入生成樹 k=minimum(closedge); /求:加入生成樹的下一個(gè)頂點(diǎn)w的存儲(chǔ)位置k printf(closedgek.adjvex,G.vexsk); /輸出新加入生成樹的邊 closedgek.lowcost=0; /頂點(diǎn)w并入U(xiǎn)集 for(j=0;jG.vexnum;+j) /更

19、新closedge數(shù)組 if(G.arcskj.adjclosedgej.lowcost) /從w發(fā)向V-U集各頂點(diǎn)的邊的權(quán)更小時(shí)，更新closedgej closedgej=G.vexsk,G.arcskj.adj; /j的關(guān)聯(lián)點(diǎn)變?yōu)閣 本算法時(shí)間復(fù)雜度：O(n2)-循環(huán)i嵌套循環(huán)j2022/7/22考研輔導(dǎo)最小生成樹克魯斯卡爾算法基本思想（加邊法） 設(shè)連通網(wǎng)為N=V,E，生成樹為T。將n個(gè)頂點(diǎn)看成n個(gè)集合;按權(quán)值由小到大的順序選擇邊，且邊的兩個(gè)頂點(diǎn)不在同一頂點(diǎn)集內(nèi)。將該邊加入生成樹，并將該邊的兩個(gè)頂點(diǎn)所在集合合并；重復(fù)直至所有頂點(diǎn)都在同一集合內(nèi)。6155563426V1V2V6V3V5V4

20、V1V251V6V3V5V4342return2022/7/22考研輔導(dǎo)拓?fù)渑判駻OV-網(wǎng) 用頂點(diǎn)表示活動(dòng)，弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)（Activity On Network），簡稱AOV-網(wǎng)。拓?fù)渑判蛴赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判?。從有向圖中選取一個(gè)沒有前驅(qū)的頂點(diǎn)，并輸出它；從有向圖中刪除該頂點(diǎn)和所有以它為尾的弧。重復(fù)直至所有頂點(diǎn)均已輸出或當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)。后者說明有向圖中存在環(huán)。V1V2V6V3V5V4拓?fù)渑判蛐蛄校篤1 V2 V4 V6 V3 V52022/7/22考研輔導(dǎo)/有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無回路，則

21、輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K，否則ERROR。 算法7.12 Status Topologicaisort(ALGraph G) FindInDegree(G,indegree); /對(duì)各頂點(diǎn)求入度,indegree為數(shù)組 InitStack(S); /為零入度頂點(diǎn)建立棧S for(i=0;iNextarc) /對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1,即刪除由i號(hào)頂點(diǎn)發(fā)出的各條弧 k=p-adjvex; if(!(-indegreek) Push(S,k); /若入度為零，則入棧 if(countG.vexnum) return ERROR ; /圖中有回路 else return OK;本

22、算法時(shí)間復(fù)雜度：O(n+e)return2022/7/22考研輔導(dǎo)關(guān)鍵路徑關(guān)鍵路徑有向網(wǎng)中，頂點(diǎn)表示事件，弧表示活動(dòng)，弧上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間。該網(wǎng)絡(luò)稱之為AOE-網(wǎng)(Activity On Edge)。 假設(shè)以AOE-網(wǎng)表示一個(gè)施工流圖，則有待研究的問題是： 完成整項(xiàng)工程至少需要多少時(shí)間？ 哪些子工程是影響整個(gè)工程進(jìn)度的關(guān)鍵？整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長路徑?！瓣P(guān)鍵活動(dòng)”指的是：該活動(dòng)的持續(xù)時(shí)間的增加會(huì)使有向圖上的最長路徑的長度增加。2022/7/22考研輔導(dǎo)關(guān)鍵路徑如何求關(guān)鍵路徑？“事件(頂點(diǎn)vi)”的最早發(fā)生時(shí)間ve(i)：指事件最早也得在以它為匯點(diǎn)的所有子工程完

23、成后才能開始。 ve(i)=從源點(diǎn)到頂點(diǎn)Vi的最長路徑長度；“事件(頂點(diǎn)vi)”的最晚發(fā)生時(shí)間vl(i)：表示在不推遲整個(gè)工程完成的前提下，事件最晚發(fā)生的時(shí)間。即事件無論發(fā)生多晚，最后也得保證它后面的子工程中最長工期的子工程要按時(shí)完成。vl(i)=工程完成時(shí)間-從頂點(diǎn)Vi到匯點(diǎn)的最長路徑長度。 活動(dòng)的最早開始時(shí)間e(i)：取決于該活動(dòng)前的事件的最早發(fā)生時(shí)間。 活動(dòng)的最晚開始時(shí)間l(i)：取決于該活動(dòng)后的事件的最晚發(fā)生時(shí)間。關(guān)鍵活動(dòng)：e(i)=l(i)的那些活動(dòng)。關(guān)鍵路徑：由關(guān)鍵活動(dòng)組成的路徑。2022/7/22考研輔導(dǎo)關(guān)鍵路徑事件發(fā)生時(shí)間的計(jì)算：如圖：假設(shè)事件為vi,vj，弧為，活動(dòng)為a： 事件最早開始時(shí)間: ve(源點(diǎn))=0； ve(j)=Maxve(i)+dut() T,j=1,2,n-1 其中，T是所有以第j個(gè)頂點(diǎn)為頭的弧的集合。 說明：在求某個(gè)ve(j)時(shí)，可能有多個(gè)i存在，即Vj有多個(gè)前驅(qū)頂點(diǎn)。 事件最晚開始時(shí)間 vl(匯點(diǎn))=ve(匯點(diǎn))； vl(i)=Minvl(j)dut() S,i=n-2,0 其中，S是所有以第i個(gè)頂點(diǎn)為尾的弧的集合。 說明：在求某個(gè)vl(i)時(shí)，可能有多個(gè)j存在，即Vi有多個(gè)后繼頂點(diǎn)。 求ve(j)的順序應(yīng)該是按拓?fù)溆行虻拇涡颉?求vl(i)的順序應(yīng)該是按拓?fù)淠嫘虻拇涡??；?/p>