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

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

是V的子集，且VR’

是VR的子集，則稱G’

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

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

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

有路徑，則稱V和V’

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

④

①

②

③

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

數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。

數(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第十九頁，共四十五頁，編輯于2023年，星期三基本操作CreateGraph(&G,V,VR);//按V和VR的定義構(gòu)造圖GDestroyGraph(&G);//銷毀圖GLocateVex(G,u);//若G中存在頂點u，則返回該頂點//在圖中位置；否則返回其它信息GetVex(G,v);//返回v的值PutVex(&G,v,value);//對v賦值valueFirstAdjVex(G,v);//返回v的第一個鄰接點。//若v在G中沒有鄰接點，則返回“空”第二十頁，共四十五頁，編輯于2023年，星期三NextAdjVex(G,v,w);//返回v的(相對于w的)下一

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

CADB

CABDCBAA=0111101111011110A

B

C

DA

B

C

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

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

表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。InfoType*info;//指向該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//描述頂點的數(shù)組AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧(邊)數(shù)GraphKindkind;//圖的種類標(biāo)志}MGraph;第二十九頁，共四十五頁，編輯于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)造無向圖G

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

default：returnERROR；

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

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

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

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)；//輸入一條邊依附的頂點及權(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>的對稱弧<v2,v1>}returnOK;}//CreateUDN第三十一頁，共四十五頁，編輯于2023年，星期三2.圖的鄰接表存儲表示類似樹的孩子鏈表。即對圖中的每個頂點vi建立一個單鏈表，表中結(jié)點表示依附于該頂點vi的邊或弧。鄰接點域鏈域數(shù)據(jù)域指示與頂點vi鄰接的點在圖中的位置指示下一條邊或弧的結(jié)點存儲和邊或弧相關(guān)的信息數(shù)據(jù)域鏈域指向鏈表第一個結(jié)點存儲頂點vi和其他有關(guān)信息表結(jié)點表頭結(jié)點第三十二頁，共四十五頁，編輯于2023年，星期三V1V3V2V4V1V3V2V4例如：∧1∧3∧4

4

3

2

1∧4

4

3

2

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

4

3

2

1∧1

∧

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

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

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

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

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