數(shù)據(jù)結(jié)構(gòu)第講圖的定義與存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)第講圖的定義與存儲(chǔ)結(jié)構(gòu)第一頁(yè)，共四十五頁(yè)，編輯于2023年，星期三課程先后關(guān)系如圖：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11第二頁(yè)，共四十五頁(yè)，編輯于2023年，星期三第7章圖7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問(wèn)題7.5有向無(wú)環(huán)圖及其應(yīng)用7.6最短路徑第三頁(yè)，共四十五頁(yè)，編輯于2023年，星期三7.1圖的定義和術(shù)語(yǔ)1.基本術(shù)語(yǔ)(1)頂點(diǎn)圖中的數(shù)據(jù)元素通常稱(chēng)為頂點(diǎn)。V是頂點(diǎn)的有窮非空集合；VR是兩個(gè)頂點(diǎn)之間的關(guān)系的集合。(2)有向圖若稱(chēng)<v,w>∈VR表示從v到w的一條弧，且稱(chēng)v為弧尾或初始點(diǎn)，稱(chēng)w為弧頭或終端結(jié)點(diǎn)，則該圖稱(chēng)為有向圖。第四頁(yè)，共四十五頁(yè)，編輯于2023年，星期三(3)無(wú)向圖若<v,w>∈VR，必有<w,v>∈VR，即VR是對(duì)稱(chēng)的，則以無(wú)序?qū)Γ╲,w)代替這兩個(gè)有序?qū)Γ硎緑和w之間的一條邊，則該圖稱(chēng)為無(wú)向圖。第五頁(yè)，共四十五頁(yè)，編輯于2023年，星期三(4)權(quán)/網(wǎng)有時(shí)圖的邊或弧具有與它相關(guān)的數(shù)，這些數(shù)稱(chēng)為權(quán)值（通常表示頂點(diǎn)間的距離或耗費(fèi)），則帶權(quán)值的圖稱(chēng)為網(wǎng)。(5)子圖假設(shè)有兩個(gè)圖G=（V，{VR}）和G’=（V’，{VR’}），若V’

是V的子集，且VR’

是VR的子集，則稱(chēng)G’

為G的子圖。第六頁(yè)，共四十五頁(yè)，編輯于2023年，星期三G1的子圖G2的子圖第七頁(yè)，共四十五頁(yè)，編輯于2023年，星期三(6)完全圖假設(shè)用n表示圖中頂點(diǎn)的數(shù)目，用e表示邊或弧的數(shù)目。忽略自身弧/邊，即若﹤vi,vj﹥∈VR，則vi≠vj。對(duì)于無(wú)向圖，有(n(n-1))/2條邊的無(wú)向圖稱(chēng)為完全圖。對(duì)于有向圖，有n(n-1)條弧的有向圖稱(chēng)為有向完全圖。(7)稀疏圖/稠密圖邊或弧很少（如e＜nlogn）的圖稱(chēng)稀疏圖，反之稱(chēng)稠密圖。第八頁(yè)，共四十五頁(yè)，編輯于2023年，星期三(8)鄰接點(diǎn)對(duì)于無(wú)向圖G=(V,{E})，若邊(v,v’)∈E，則稱(chēng)頂點(diǎn)v和v’互為鄰接點(diǎn)，即v和v’相鄰接?；蚍Q(chēng)邊（v,v’）依附于頂點(diǎn)v和v’，或稱(chēng)（v,v’）和頂點(diǎn)v和v’

相關(guān)聯(lián)。對(duì)于有向圖G=(V，{E})，若弧<v，v’>∈E，則稱(chēng)頂點(diǎn)v鄰接到頂點(diǎn)v’，或稱(chēng)頂點(diǎn)v’鄰接自頂點(diǎn)v，或弧<v，v’>和頂點(diǎn)v，v’

相關(guān)聯(lián)。(a)(b)第九頁(yè)，共四十五頁(yè)，編輯于2023年，星期三頂點(diǎn)的入度/出度以頂點(diǎn)v為頭的弧的數(shù)目稱(chēng)v的入度，記為ID(v)；以頂點(diǎn)v為尾的弧的數(shù)目稱(chēng)v的出度，記為OD(v)。頂點(diǎn)v的度TD（v）=ID（v）＋OD（v）(9)頂點(diǎn)v的度(Degree)是和v相關(guān)聯(lián)的邊的數(shù)目，記為T(mén)D（v）。(a)(b)第十頁(yè)，共四十五頁(yè)，編輯于2023年，星期三(10)路徑(Path)無(wú)向圖G=(V,{E})中，從頂點(diǎn)v到v’的路徑是頂點(diǎn)序列(v=vi0,vi1,…,vim=v’)，其中(vij-1,vij)∈E，1≤j≤m。若G是有向圖，則路徑也是有向的，頂點(diǎn)序列應(yīng)滿足：<vij-1,vij>∈E，1≤j≤m。路徑的長(zhǎng)度是路徑上的邊或弧的數(shù)目。第十一頁(yè)，共四十五頁(yè)，編輯于2023年，星期三(11)回路/環(huán)/簡(jiǎn)單路徑第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱(chēng)為回路/環(huán)。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱(chēng)為簡(jiǎn)單路徑。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱(chēng)為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。第十二頁(yè)，共四十五頁(yè)，編輯于2023年，星期三(12)連通圖/連通分量在無(wú)向圖G中，如果從頂點(diǎn)V到頂點(diǎn)V’

有路徑，則稱(chēng)V和V’

是連通的。若圖中任意兩個(gè)頂點(diǎn)vi、vj∈V，vi和vj都是連通的，則稱(chēng)G是連通圖。無(wú)向圖中的極大連通子圖稱(chēng)之為連通分量。第十三頁(yè)，共四十五頁(yè)，編輯于2023年，星期三左圖：連通圖下圖：非連通圖，但有三個(gè)連通分量第十四頁(yè)，共四十五頁(yè)，編輯于2023年，星期三(13)強(qiáng)連通圖/強(qiáng)連通分量在有向圖G中，若對(duì)于每一對(duì)vi、vj∈V，vi≠vj，從vi到vj和從vj到vi都存在路徑，則稱(chēng)G是強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱(chēng)作有向圖的強(qiáng)連通分量。第十五頁(yè)，共四十五頁(yè)，編輯于2023年，星期三非強(qiáng)連通圖

④

①

②

③

④①②③兩個(gè)強(qiáng)連通分量第十六頁(yè)，共四十五頁(yè)，編輯于2023年，星期三一個(gè)連通圖的生成樹(shù)是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹(shù)的n-1條邊。如果在一棵生成樹(shù)上添加一條邊，必定構(gòu)成一個(gè)環(huán)，因?yàn)檫@條邊使得它依附的那兩個(gè)頂點(diǎn)之間有了第二條路徑。(14)生成樹(shù)第十七頁(yè)，共四十五頁(yè)，編輯于2023年，星期三如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則是一棵有向樹(shù)。一個(gè)有向圖的生成森林由若干棵有向樹(shù)組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹(shù)的弧。(15)生成森林第十八頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2.圖的抽象類(lèi)型定義ADTGraph{

數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱(chēng)為頂點(diǎn)集。

數(shù)據(jù)關(guān)系R：R={VR}VR={<v,w>|v,w∈V且P(v,w)，<v,w>

表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}

基本操作P：}ADTGraph第十九頁(yè)，共四十五頁(yè)，編輯于2023年，星期三基本操作CreateGraph(&G,V,VR);//按V和VR的定義構(gòu)造圖GDestroyGraph(&G);//銷(xiāo)毀圖GLocateVex(G,u);//若G中存在頂點(diǎn)u，則返回該頂點(diǎn)//在圖中位置；否則返回其它信息GetVex(G,v);//返回v的值PutVex(&G,v,value);//對(duì)v賦值valueFirstAdjVex(G,v);//返回v的第一個(gè)鄰接點(diǎn)。//若v在G中沒(méi)有鄰接點(diǎn)，則返回“空”第二十頁(yè)，共四十五頁(yè)，編輯于2023年，星期三NextAdjVex(G,v,w);//返回v的(相對(duì)于w的)下一

//個(gè)鄰接點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn)，則“空”InsertVex(&G,v);//在圖G中增添新頂點(diǎn)v。DeleteVex(&G,v);//刪除G中頂點(diǎn)v及其相關(guān)的弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G//是無(wú)向的，則還增添對(duì)稱(chēng)弧<w,v>DeleteArc(&G,v,w);//在G中刪除弧<v,w>，若G//是無(wú)向的，則還刪除對(duì)稱(chēng)弧<w,v>第二十一頁(yè)，共四十五頁(yè)，編輯于2023年，星期三DFSTraverse(G,v,Visit());//從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用//函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());//從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用//函數(shù)Visit一次且僅一次。第二十二頁(yè)，共四十五頁(yè)，編輯于2023年，星期三第7章圖7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問(wèn)題7.5有向無(wú)環(huán)圖及其應(yīng)用7.6最短路徑第二十三頁(yè)，共四十五頁(yè)，編輯于2023年，星期三7.2圖的存儲(chǔ)結(jié)構(gòu)圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示有向圖的十字鏈表存儲(chǔ)表示無(wú)向圖的鄰接多重表存儲(chǔ)表示第二十四頁(yè)，共四十五頁(yè)，編輯于2023年，星期三1.圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示鄰接矩陣是用于描述圖中頂點(diǎn)之間關(guān)系(即弧或邊的權(quán))的矩陣。假設(shè)圖中頂點(diǎn)數(shù)為n，則鄰接矩陣An×n：1若Vi和Vj之間有弧或邊A[i][j]=0反之第二十五頁(yè)，共四十五頁(yè)，編輯于2023年，星期三

CADB

CABDCBAA=0111101111011110A

B

C

DA

B

C

CBAB=010100110第二十六頁(yè)，共四十五頁(yè)，編輯于2023年，星期三注意：1)圖中無(wú)鄰接到自身的弧，因此鄰接矩陣主對(duì)角線為全零。2)無(wú)向圖的鄰接矩陣必然是對(duì)稱(chēng)矩陣。3)無(wú)向圖中，頂點(diǎn)的度是鄰接矩陣對(duì)應(yīng)行（或列）的非零元素之和；有向圖中，對(duì)應(yīng)行的非零元素之和是該頂點(diǎn)的出度；對(duì)應(yīng)列的非零元素之和是該頂點(diǎn)的入度；則該頂點(diǎn)的度是對(duì)應(yīng)行和對(duì)應(yīng)列的非零元素之和。第二十七頁(yè)，共四十五頁(yè)，編輯于2023年，星期三V1V2V3V4V5V65485931567網(wǎng)的鄰接矩陣

∞反之權(quán)值若Vi和Vj之間有弧或邊A[i][j]=第二十八頁(yè)，共四十五頁(yè)，編輯于2023年，星期三圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大頂點(diǎn)個(gè)數(shù)typedefenum{DG,DN,UDG,UDN}GraphKind;//圖類(lèi)型（有向圖/網(wǎng),無(wú)向圖/網(wǎng)）typedefstructArcCell{VRTypeadj;//VRType是頂點(diǎn)關(guān)系類(lèi)型。對(duì)無(wú)權(quán)圖，用1或0

表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型。InfoType*info;//指向該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//描述頂點(diǎn)的數(shù)組AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù)GraphKindkind;//圖的種類(lèi)標(biāo)志}MGraph;第二十九頁(yè)，共四十五頁(yè)，編輯于2023年，星期三構(gòu)造圖的算法StatusCreateGraph(Mgraph&G){//采用數(shù)組(鄰接矩陣)表示法，構(gòu)造圖G。

scanf(&G.kind)；

switch(G.kind){

caseDG：returnCreateDG(G)；//構(gòu)造有向圖G

caseDN：returnCreateDN(G)；//構(gòu)造有向網(wǎng)G

caseUDG：returnCreateUDG(G)；//構(gòu)造無(wú)向圖G

caseUDN：returnCreateUDN(G)；//構(gòu)造無(wú)向網(wǎng)G

default：returnERROR；

}}//CreateGraph第三十頁(yè)，共四十五頁(yè)，編輯于2023年，星期三采用數(shù)組表示法，構(gòu)造無(wú)向網(wǎng)GStatusCreateUDN(MGraph&G){

sacnf(&G.vexnum,&G.arcnum,&IncInfo);

for(i=0;i<G.vexnum;++i)scanf(&G.vexs[i]);//構(gòu)造頂點(diǎn)向量

for(i=0；i<G.vexnum；++i)

//初始化鄰接矩陣

for(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};//{adj,info}

for(k=0；k<G.arcnum；++k){

//構(gòu)造鄰接矩陣

scanf(&v1，&v2，&w)；//輸入一條邊依附的頂點(diǎn)及權(quán)值

i=LocateVex(G,v1);j=LocateVex(G,v2);//v1和v2在G中位置

G.arcs[i][j].adj=w；//弧<v1，v2>的權(quán)值

if(IncInfo)Input(*G.arcs[i][j].info);G.arcs[j][i]=G.arcs[i][j];//置<v1,v2>的對(duì)稱(chēng)弧<v2,v1>}returnOK;}//CreateUDN第三十一頁(yè)，共四十五頁(yè)，編輯于2023年，星期三2.圖的鄰接表存儲(chǔ)表示類(lèi)似樹(shù)的孩子鏈表。即對(duì)圖中的每個(gè)頂點(diǎn)vi建立一個(gè)單鏈表，表中結(jié)點(diǎn)表示依附于該頂點(diǎn)vi的邊或弧。鄰接點(diǎn)域鏈域數(shù)據(jù)域指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置指示下一條邊或弧的結(jié)點(diǎn)存儲(chǔ)和邊或弧相關(guān)的信息數(shù)據(jù)域鏈域指向鏈表第一個(gè)結(jié)點(diǎn)存儲(chǔ)頂點(diǎn)vi和其他有關(guān)信息表結(jié)點(diǎn)表頭結(jié)點(diǎn)第三十二頁(yè)，共四十五頁(yè)，編輯于2023年，星期三V1V3V2V4V1V3V2V4例如：∧1∧3∧4

4

3

2

1∧4

4

3

2

121∧113∧4∧4∧2第三十三頁(yè)，共四十五頁(yè)，編輯于2023年，星期三注意：在無(wú)向圖的鄰接表中，1）第i個(gè)鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的度；2）所有鏈表中結(jié)點(diǎn)數(shù)目的一半為圖中邊數(shù)；3）占用的存儲(chǔ)單元數(shù)目為n+2e。在有向圖的鄰接表中，1）第i個(gè)鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的出度；2）所有鏈表中結(jié)點(diǎn)數(shù)目為圖中弧數(shù)；3）占用的存儲(chǔ)單元數(shù)目為n+e。第三十四頁(yè)，共四十五頁(yè)，編輯于2023年，星期三為求出每一個(gè)頂點(diǎn)的入度，必須另外建立有向圖的逆鄰接表。有向圖的逆鄰接表與鄰接表類(lèi)似，只是它是從入度考慮結(jié)點(diǎn)，而不是從出度考慮結(jié)點(diǎn)。2∧4

4

3

2

1∧1

∧

逆鄰接表∧3V1V3V2V4第三十五頁(yè)，共四十五頁(yè)，編輯于2023年，星期三圖的鄰接表存儲(chǔ)表示#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//該弧所指向的頂點(diǎn)的位置structArcNode*nextarc;//指向下一條弧的指針I(yè)nfoType*info;//該弧相關(guān)信息的指針}ArcNode;typedefstructVNode{VertexTypedata;//頂點(diǎn)信息ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)intkind;//圖的種類(lèi)標(biāo)志}ALGraph;第三十六頁(yè)，共四十五頁(yè)，編輯于2023年，星期三3.有向圖的十字鏈表存儲(chǔ)表示十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?？梢岳斫獬捎邢驁D的鄰接表和逆鄰接表的結(jié)合，在十字鏈表中，有兩種結(jié)點(diǎn)結(jié)構(gòu)：尾域tailvex頭域headvex鏈域hlink鏈域tlink信息域info數(shù)據(jù)域data鏈域firstin鏈域firstout頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)第三十七頁(yè)，共四十五頁(yè)，編輯于2023年，星期三尾域tv指示弧尾頂點(diǎn)在圖中的位置頭域hv指示弧頭頂點(diǎn)在圖中的位置鏈域h指向弧頭相同的下一條弧鏈域t指向弧尾相同的下一條弧信息域指向該弧的相關(guān)信息尾域tailvex頭域headvex鏈域hlink鏈域tlink信息域info數(shù)據(jù)域data鏈域firstin鏈域firstout數(shù)據(jù)域存儲(chǔ)和頂點(diǎn)相關(guān)信息鏈域fin指向以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)鏈域fout指向以該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)第三十八頁(yè)，共四十五頁(yè)，編輯于2023年，星期三v1v2v3v4

012310/\20v3v1v4v2/\03/\13/\/\2302/\/\32例：datafirstinfirstouttailvexheadvexhlinktlink/\第三十九頁(yè)，共四十五頁(yè)，編輯于2023年，星期三有向圖的十字鏈表存儲(chǔ)表示#defineMAX_VERTEX_NUM20typedefstructArcBox{inttailvex,headvex;//該弧的尾和頭頂點(diǎn)的位置structArcBox*hlink,*tlink;//分別指向下一個(gè)弧頭相同

和弧尾相同的弧的指針域InfoType*info;//該弧相關(guān)信息的指針}ArcBox;typedefstructVexNode{VertexTypedata;

ArcBox*firstin,*firstout;//分別指向該頂點(diǎn)第一條入弧和出弧}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//表頭向量intvexnum,arcnum;//有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}OLGraph;第四十頁(yè)，共四十五頁(yè)，編輯于2023年，星期三4.無(wú)向圖的鄰接多重表存儲(chǔ)表示在無(wú)向圖的鄰接表中，每條邊（Vi，Vj）由兩個(gè)結(jié)點(diǎn)表示，一個(gè)結(jié)點(diǎn)在第i個(gè)鏈表中，另一個(gè)結(jié)點(diǎn)在第j個(gè)鏈表中，當(dāng)需要對(duì)邊進(jìn)行操作時(shí)，就需找到表示同一條邊的兩個(gè)結(jié)點(diǎn)，這給操作帶來(lái)不便，在這種情況下采用鄰接多重表較方便。

鄰接多重表中結(jié)點(diǎn)分為：邊結(jié)點(diǎn)