圖的定義和術(shù)語(yǔ)及存儲(chǔ)結(jié)構(gòu)

圖的定義和術(shù)語(yǔ)及存儲(chǔ)結(jié)構(gòu)第1頁(yè)，共35頁(yè)，2023年，2月20日，星期六17.1基本術(shù)語(yǔ)7.2存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性7.5圖的應(yīng)用第7章圖第2頁(yè)，共35頁(yè)，2023年，2月20日，星期六27.1圖的基本術(shù)語(yǔ)其中：V

是G的頂點(diǎn)集合，是有窮非空集；

VR＝{<v,w>|v,w∈V且P(v,w)},是有窮集.問(wèn)：當(dāng)VR為空時(shí)，圖G存在否？V=vertex圖：記為

Graph＝(

V,VR)EACBD<v,w>表示從v到w的一條弧，并稱w為弧頭，v為弧尾。P(v,w)定義了弧<v,w>的意義或信息。答：還存在！但此時(shí)圖G只有頂點(diǎn)。第3頁(yè)，共35頁(yè)，2023年，2月20日，星期六3EACBD例如:G=(V,VR)其中V={A,B,C,D,E}VR={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}無(wú)向圖：由頂點(diǎn)集和邊集構(gòu)成的圖(“邊”無(wú)方向）若<v,w>VR必有<w,v>VR,則稱(v,w)

為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊。有向圖：由頂點(diǎn)集和弧集構(gòu)成的圖（“弧”是有方向的）第4頁(yè)，共35頁(yè)，2023年，2月20日，星期六4BCAFED例如:

G=(V,VR)其中：V={A,B,C,D,E,F}VR={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}若

n個(gè)頂點(diǎn)的無(wú)向圖有

n(n-1)/2條邊,

稱為無(wú)向完全圖若

n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,稱為有向完全圖證明：①有向完全圖有n(n-1)條邊。證明：若是有向完全圖，則n個(gè)頂點(diǎn)中的每個(gè)頂點(diǎn)都有一條弧指向其它n-1個(gè)頂點(diǎn),因此總邊數(shù)=n(n-1)1234第5頁(yè)，共35頁(yè)，2023年，2月20日，星期六5證明：從①可以直接推論出無(wú)向完全圖的邊數(shù)——因?yàn)闊o(wú)方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為n(n-1)/2。②無(wú)向完全圖有n(n-1)/2條邊。1234例：判斷下列4種圖形各屬什么類型？第6頁(yè)，共35頁(yè)，2023年，2月20日，星期六6稀疏圖：

稠密圖：設(shè)有兩個(gè)圖G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,則稱圖G’是圖G的子圖。子圖：邊較少的圖。通常邊數(shù)遠(yuǎn)少于nlogn邊很多的圖。無(wú)向圖中，邊數(shù)接近n(n-1)/2有向圖中，邊數(shù)接近n(n-1)BBCABECFABECF例如：第7頁(yè)，共35頁(yè)，2023年，2月20日，星期六7ABECF1597211132有向網(wǎng)或無(wú)向網(wǎng)是弧或邊帶權(quán)的圖。鄰接點(diǎn)：若邊(v,w)∈VR，則頂點(diǎn)v和頂點(diǎn)w互為鄰接點(diǎn)。

邊(v,w)依附于頂點(diǎn)v和w，或者與頂點(diǎn)v,w相關(guān)聯(lián)。頂點(diǎn)v的度：是和v相關(guān)聯(lián)的邊的數(shù)目,記為TD(v).頂點(diǎn)v的出度:

以頂點(diǎn)v

為尾的弧的數(shù)目;記為OD(v).頂點(diǎn)v的入度:

以頂點(diǎn)v

為頭的弧的數(shù)目,記為ID(v).頂點(diǎn)的度(TD)=出度(OD)+入度(ID)問(wèn)：當(dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時(shí)是何形狀？答：是樹(shù)！而且是一棵有向樹(shù)！第8頁(yè)，共35頁(yè)，2023年，2月20日，星期六8路徑:設(shè)圖G=(V,VR)中的一個(gè)頂點(diǎn)序列:v=vi,0,vi,1,…,vi,m=w中，(vi,j-1,vi,j)（或〈vi,j-1,vi,j〉）

VR

1≤j≤m,則稱從頂點(diǎn)v

到頂點(diǎn)w

之間存在一條路徑。路徑長(zhǎng)度：路徑上邊（或?。┑臄?shù)目。ABECF如:從A到F長(zhǎng)度為3的路徑{A,B,C,F}或{A，E，C，F(xiàn)}簡(jiǎn)單路徑:指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路:指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路。第9頁(yè)，共35頁(yè)，2023年，2月20日，星期六9連通圖：無(wú)向圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相連通。連通分量：非連通圖中的極大連通子圖。BACDFEBACDFE強(qiáng)連通圖：在有向圖中,每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑強(qiáng)連通分量：非強(qiáng)連通圖中的極大強(qiáng)連通子圖。ABECFABECF第10頁(yè)，共35頁(yè)，2023年，2月20日，星期六10生成樹(shù)：v1v2v3v4生成森林：假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊，其中n-1條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹(shù)。由若干棵生成樹(shù)組成，含全部頂點(diǎn)，但構(gòu)成這些樹(shù)的邊是最少的。（對(duì)有向或無(wú)向圖均適用）第11頁(yè)，共35頁(yè)，2023年，2月20日，星期六11CreatGraph(&G,V,VR)//按定義(V,VR)構(gòu)造圖DestroyGraph(&G)

//銷毀圖結(jié)構(gòu)的建立和銷毀對(duì)頂點(diǎn)的訪問(wèn)操作LocateVex(G,u)

//若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中“位置”，否則返回其它信息。GetVex(G,v)

//返回v的值。PutVex(&G,v,value)

//對(duì)v賦值value。結(jié)構(gòu)的建立和銷毀插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作遍歷插入或刪除弧基本操作對(duì)頂點(diǎn)的訪問(wèn)操作第12頁(yè)，共35頁(yè)，2023年，2月20日，星期六12對(duì)鄰接點(diǎn)的操作FirstAdjVex(G,v);//返回v的“第一個(gè)鄰接點(diǎn)”若該頂點(diǎn)在G中沒(méi)有鄰接點(diǎn)，則返回“空”。NextAdjVex(G,v,w);//返回v的（相對(duì)于w的）“下一個(gè)鄰接點(diǎn)”。若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”。插入或刪除頂點(diǎn)InsertVex(&G,v);

//在圖G中增添新頂點(diǎn)v。DeleteVex(&G,v)；//刪除G中頂點(diǎn)v及其相關(guān)的弧。第13頁(yè)，共35頁(yè)，2023年，2月20日，星期六13插入和刪除弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是無(wú)向的，則還增添對(duì)稱弧<w,v>。DeleteArc(&G,v,w);//在G中刪除弧<v,w>，若G是無(wú)向的，則還刪除對(duì)稱弧<w,v>。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一次且僅一次。遍歷第14頁(yè)，共35頁(yè)，2023年，2月20日，星期六147.2圖的存儲(chǔ)結(jié)構(gòu)圖的特點(diǎn)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：難！（多個(gè)頂點(diǎn)，無(wú)序可言，無(wú)法僅以頂點(diǎn)坐標(biāo)表達(dá)相互關(guān)系）可用多重鏈表鄰接矩陣(數(shù)組)表示法鄰接表(鏈?zhǔn)?表示法十字鏈表表示法鄰接多重表表示法但可用數(shù)組描述元素間關(guān)系。非線性結(jié)構(gòu)（m:n）鄰接矩陣鄰接表十字鏈表鄰接多重表各種表示法成立的原則：存入電腦后能唯一復(fù)原第15頁(yè)，共35頁(yè)，2023年，2月20日，星期六15①建立一個(gè)頂點(diǎn)表和一個(gè)鄰接矩陣。1.鄰接矩陣（數(shù)組）表示法記錄各個(gè)頂點(diǎn)信息表示各個(gè)頂點(diǎn)之間關(guān)系②設(shè)圖A=(V,E)有n個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組A.arcs[n][n]，定義為：第16頁(yè)，共35頁(yè)，2023年，2月20日，星期六16分析1：無(wú)向圖的鄰接矩陣是對(duì)稱的；分析2：頂點(diǎn)i

的度＝第i

行(列)中1的個(gè)數(shù)；特別：完全圖的鄰接矩陣中，對(duì)角元素為0，其余全1。例1：鄰接矩陣：A.arcs=（v1v2

v3v4v5）v1v2v3v4v501

0

1010

1010

10111010101110頂點(diǎn)表：無(wú)向圖的鄰接矩陣如何表示？v1v2v3v5v4v4A第17頁(yè)，共35頁(yè)，2023年，2月20日，星期六17例2：有向圖的鄰接矩陣如何表示？分析1：有向圖的鄰接矩陣可能是不對(duì)稱的。分析2：頂點(diǎn)vi的出度=第i行元素之和;

頂點(diǎn)vi的入度=第i列元素之和;

頂點(diǎn)的度=第i行元素之和+第i列元素之和。v1v2v3v4A鄰接矩陣：A.arcs=(v1v2

v3v4)v1v2v3v4注：在有向圖的鄰接矩陣中，第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）；第j列含義：以結(jié)點(diǎn)vj為頭的弧(即入度邊）。頂點(diǎn)表：01

1

000

000

001

1000第18頁(yè)，共35頁(yè)，2023年，2月20日，星期六18例3：有權(quán)圖（即網(wǎng)絡(luò)）的鄰接矩陣如何表示？定義：A.arcs[i][j]=Wij<vi,vj>或（vi,vj）∈VR∞反之v1v2v3v4Nv5v65489755613鄰接矩陣：N.arcs=(v1v2

v3v4v5v6)頂點(diǎn)表：∞

5

∞

7∞

∞∞

∞

4

∞∞

∞8

∞

∞

∞∞

9∞

∞

5∞∞

6∞

∞

∞

5∞

∞

3

∞

∞∞1

∞v1v2v3v4v5v6第19頁(yè)，共35頁(yè)，2023年，2月20日，星期六19容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等等。

n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺點(diǎn)：對(duì)稀疏圖而言尤其浪費(fèi)空間。圖的鄰接矩陣在機(jī)內(nèi)如何表示？（參見(jiàn)教材P161）注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假設(shè)的最大頂點(diǎn)數(shù)typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向圖，有向網(wǎng)，無(wú)向圖，無(wú)向網(wǎng)}第20頁(yè)，共35頁(yè)，2023年，2月20日，星期六20typedefstructArcCell{//弧的定義

VRTypeadj;//VRType是頂點(diǎn)關(guān)系類型。//對(duì)無(wú)權(quán)圖,用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。

InfoType*info;//該弧相關(guān)信息的指針}ArcCell,

AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedefstruct{//圖的定義

VertexTypevexs[MAX_VERTEX_NUM];

//頂點(diǎn)向量

AdjMatrixarcs;

//鄰接矩陣

intvexnum,arcnum;//頂點(diǎn)數(shù)，弧數(shù)

GraphKindkind;//圖的種類標(biāo)志

}MGraph;第21頁(yè)，共35頁(yè)，2023年，2月20日，星期六212.鄰接表（鏈?zhǔn)剑┍硎痉á賹?duì)每個(gè)頂點(diǎn)vi建立一個(gè)單鏈表，把與vi有關(guān)聯(lián)的邊（或以vi為尾的弧)的信息鏈接起來(lái)，表中每個(gè)結(jié)點(diǎn)都設(shè)為3個(gè)域。②每個(gè)單鏈表還應(yīng)當(dāng)附設(shè)一個(gè)表頭結(jié)點(diǎn)（設(shè)為2個(gè)域），存vi信息；adjvexnextarcinfodatafirstarc表結(jié)點(diǎn)頭結(jié)點(diǎn)鄰接點(diǎn)域，表示vi

鄰接點(diǎn)的位置鏈域，指向下一條邊或弧的結(jié)點(diǎn)數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)vi

信息鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn)③每個(gè)單鏈表的頭結(jié)點(diǎn)另外用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。邊或弧的信息第22頁(yè)，共35頁(yè)，2023年，2月20日，星期六22例1：無(wú)向圖的鄰接表如何表示？v1v2v3v5v4v4鄰接表：01234^1334^142^0請(qǐng)注意：鄰接表不唯一！因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。v1v2v3v4v523^142^0v1鄰接點(diǎn)v4的位置此無(wú)權(quán)圖未開(kāi)第3分量TD(Vi)=單鏈表中Vi鏈接的結(jié)點(diǎn)個(gè)數(shù)第23頁(yè)，共35頁(yè)，2023年，2月20日，星期六23例2：有向圖的鄰接表如何表示？v1v2v3v4V4V3^V2V12^3^0^1鄰接表(出邊)V4V3V2V1^3^0^2^0逆鄰接表(入邊)01230123在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。OD(Vi)=鄰接表中Vi鏈接的結(jié)點(diǎn)數(shù)ID(Vi)=逆鄰接表中Vi鏈接的結(jié)點(diǎn)數(shù)TD(Vi)=OD(Vi)+ID(Vi)第24頁(yè)，共35頁(yè)，2023年，2月20日，星期六24例3：已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫出該網(wǎng)絡(luò)。8064125當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！第25頁(yè)，共35頁(yè)，2023年，2月20日，星期六25分析1：對(duì)于n個(gè)頂點(diǎn)e條邊的無(wú)向圖，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有2e個(gè)表結(jié)點(diǎn),空間效率為O(n+2e)。若是稀疏圖(e<<n2)，則比鄰接矩陣表示法O(n2)省空間。鄰接表存儲(chǔ)法的特點(diǎn)：分析2:在有向圖中，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有e個(gè)表結(jié)點(diǎn),空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。—它其實(shí)是對(duì)鄰接矩陣法的一種改進(jìn)，兩個(gè)結(jié)點(diǎn)表示一條邊或弧鄰接表的缺點(diǎn)：鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。第26頁(yè)，共35頁(yè)，2023年，2月20日，星期六26討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2.區(qū)別：①對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。②鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（e<<n2)第27頁(yè)，共35頁(yè)，2023年，2月20日，星期六27圖的鄰接表在機(jī)內(nèi)如何表示？（參見(jiàn)教材P163）#defineMAX_VERTEX_NUM20

//假設(shè)的最大頂點(diǎn)數(shù)TypedefstructArcNode{//弧結(jié)構(gòu)

intadjvex;

//該弧所指向的頂點(diǎn)位置

structArcNode*nextarcs;

//指向下一條弧的指針

InfoArc*info;

//該弧相關(guān)信息的指針}ArcNode；第28頁(yè)，共35頁(yè)，2023年，2月20日，星期六28Typedefstruct{

//圖結(jié)構(gòu)

AdjListvertics

;

//應(yīng)包含鄰接表

intvexnum,arcnum;

//應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù)

intkind;

//還應(yīng)說(shuō)明圖的種類（用標(biāo)志）}ALGraph;TypedefstructVNode{

//頂點(diǎn)結(jié)構(gòu)

VertexTypedata;

//頂點(diǎn)信息

ArcNode*firstarc;

//指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList[MAX_VERTEX_NUM];

//鄰接表

第29頁(yè)，共35頁(yè)，2023年，2月20日，星期六29

它是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

思路：將鄰接矩陣用鏈表存儲(chǔ)，是鄰接表、逆鄰接表的結(jié)合。(1)開(kāi)設(shè)弧結(jié)點(diǎn)，設(shè)5個(gè)域（每段弧是一個(gè)數(shù)據(jù)元素）(2)開(kāi)設(shè)頂點(diǎn)結(jié)點(diǎn)，設(shè)3個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素）tailvexheadvexhlinktlinkinfo弧結(jié)點(diǎn)3.十字鏈表表示法tailvex:

弧尾頂點(diǎn)位置headvex:

弧頭頂點(diǎn)位置hlink:

弧頭相同的下一弧位置tlink:

弧尾相同的下一弧位置info:

弧信息第30頁(yè)，共35頁(yè)，2023年，2月20日，星期六30

data:

頂點(diǎn)信息firstin:

以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn)firstout:

以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn)問(wèn)：n個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？順序存儲(chǔ)結(jié)構(gòu)datafirstinfirstout頂點(diǎn)結(jié)點(diǎn)十字鏈表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的入度、出度等。空間復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接表相同。第31頁(yè)，共35頁(yè)，2023年，2月20日，星期六31A