第七章圖的定義和術(shù)語(yǔ)1第1頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

線(xiàn)性結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的一對(duì)一關(guān)系。在這種結(jié)構(gòu)中，除第一個(gè)和最后一個(gè)元素外，任何一個(gè)元素都有唯一的一個(gè)直接前驅(qū)和直接后繼。

樹(shù)結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的一對(duì)多的關(guān)系。在這種結(jié)構(gòu)中，每個(gè)元素對(duì)下(層)可以有0個(gè)或多個(gè)元素相聯(lián)系，對(duì)上(層)只有唯一的一個(gè)元素相關(guān)，數(shù)據(jù)元素之間有明顯的層次關(guān)系。第2頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月 圖(Graph)是一種比線(xiàn)性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。 圖結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的多對(duì)多的關(guān)系。在這種結(jié)構(gòu)中，任意兩個(gè)元素之間可能存在關(guān)系。即結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。第3頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月7.1

圖的定義和術(shù)語(yǔ)V1V3V2V4V1V2V5V4V3圖7.1圖的示例(a)有向圖G1 (b)無(wú)向圖G2(a)(b)第4頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月7.1.1

圖的定義和術(shù)語(yǔ)

頂點(diǎn)（Vertex)：在圖中的數(shù)據(jù)元素通常稱(chēng)為頂點(diǎn)（Vertex)。約定V表示頂點(diǎn)的有窮非空集合，VR表示兩個(gè)頂點(diǎn)之間的關(guān)系的集合。

?。ˋrc）：表示兩個(gè)頂點(diǎn)v和w之間存在一個(gè)關(guān)系，用<v,w>表示頂點(diǎn)v到w的一條弧。且稱(chēng)v為弧尾（Tail）或初始點(diǎn)，稱(chēng)w為弧頭（Head）或終端點(diǎn)。此時(shí)的圖稱(chēng)為有向圖（Digraph）。其中，頂點(diǎn)偶對(duì)<v,w>的v和w之間是有序的。第5頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

無(wú)向圖(Undigraph)：若圖關(guān)系集合中，頂點(diǎn)偶對(duì)<v,w>的v和w之間是無(wú)序的，稱(chēng)圖G是無(wú)向圖。

若<v,w>屬于VR，必有<w,v>屬于VR，即VR是對(duì)稱(chēng)的。 那么用（v,w）代替這兩個(gè)有序?qū)?，表示v和w的一條邊（Edge）。第6頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月如圖7.1：設(shè)有向圖G1和無(wú)向圖G2，形式化定義分別是：G1=(V1，A1)V1={v1,v2,v3,v4}A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}G2=(V2，E2)V2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v1),(v3,v5)}第7頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月V1V3V2V4V1V2V5V4V3圖7.1圖的示例(a)有向圖G1 (b)無(wú)向圖G2(a)(b)第8頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

完全無(wú)向圖：對(duì)于無(wú)向圖，若圖中頂點(diǎn)數(shù)為n，用e表示邊的數(shù)目，則e

[0，n(n-1)/2]。具有n(n-1)/2條邊的無(wú)向圖稱(chēng)為完全無(wú)向圖。完全無(wú)向圖另外的定義是：對(duì)于無(wú)向圖G=(V，E)，若

vi，vj

V，當(dāng)vi≠vj時(shí)，有(vi,vj)

E，即圖中任意兩個(gè)不同的頂點(diǎn)間都有一條無(wú)向邊，這樣的無(wú)向圖稱(chēng)為完全無(wú)向圖。第9頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

完全有向圖：對(duì)于有向圖，若圖中頂點(diǎn)數(shù)為n，用e表示弧的數(shù)目，則e

[0，n(n-1)]。具有n(n-1)條邊的有向圖稱(chēng)為完全有向圖。完全有向圖另外的定義是：

對(duì)于有向圖G=(V，E)，若

vi，vj

V，當(dāng)vi≠vj時(shí)，有<vi,vj>

E并且<vj,

vi>

E，即圖中任意兩個(gè)不同的頂點(diǎn)間都有一條弧，這樣的有向圖稱(chēng)為完全有向圖。第10頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

有很少邊或弧的圖（e<n㏒n）的圖稱(chēng)為稀疏圖，反之稱(chēng)為稠密圖。

權(quán)(Weight)：與圖的邊和弧相關(guān)的數(shù)。權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。這種帶權(quán)的圖稱(chēng)為網(wǎng)。第11頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月子圖和生成子圖：設(shè)有圖G=(V，E)和G’=(V’，E’)，若V’

V且E’

E，則稱(chēng)圖G’是G的子圖；若V’=V且E’

E，則稱(chēng)圖G’是G的一個(gè)生成子圖。P7.2第12頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

對(duì)于無(wú)向圖G=(V，E)，若邊(v,w)

E，則稱(chēng)頂點(diǎn)v和w互為鄰接點(diǎn)，即v和w相鄰接。邊(v,w)依附(incident)于頂點(diǎn)v和w，或者說(shuō)(v,w)和頂點(diǎn)v和w相關(guān)聯(lián)。

圖G中和v相關(guān)聯(lián)的邊的數(shù)目稱(chēng)為頂點(diǎn)v的度(degree)，記為T(mén)D(v)。例如無(wú)向圖G2。TD(V1)，TD(V2)，TD(V3)，TD(V4)，TD(V5)V1V2V5V4V3G2第13頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

對(duì)于有向圖G=(V，E)，若有向弧<v,w>

E，則稱(chēng)頂點(diǎn)v

“鄰接到”頂點(diǎn)w，頂點(diǎn)w“鄰接自”頂點(diǎn)v，弧<v,w>與頂點(diǎn)v和w

“相關(guān)聯(lián)”。

對(duì)有向圖G=(V，E)，若

vi

V，圖G中以頂點(diǎn)v作為尾或初始的有向邊(弧)的數(shù)目稱(chēng)為頂點(diǎn)v的出度(Outdegree)，記為OD(v)；以v作為頭或終點(diǎn)的有向邊(弧)的數(shù)目稱(chēng)為頂點(diǎn)v的入度(Indegree)，記為ID(v)。頂點(diǎn)v的出度與入度之和稱(chēng)為v的度，記為T(mén)D(v)。即 TD(v)=OD(v)+ID(v)第14頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月例如圖7.1所示的無(wú)向圖。OD(v1)，ID(,1)，TD(v1)；OD(v3)，ID(,3)，TD(v1)V1V3V2V4(G1)第15頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月一般地，如果頂點(diǎn)vi在的度記為T(mén)D(vi)，那么一個(gè)有n個(gè)頂點(diǎn)，e條邊或弧的圖，滿(mǎn)足：∑TD(vi)=2e第16頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

路徑(Path)

：對(duì)無(wú)向圖G=(V，E)，若從頂點(diǎn)vi經(jīng)過(guò)若干條邊能到達(dá)vj，稱(chēng)頂點(diǎn)vi和vj是連通的，又稱(chēng)頂點(diǎn)vi到vj有路徑。對(duì)有向圖G=(V，E)，從頂點(diǎn)vi到vj有有向路徑，指的是從頂點(diǎn)vi經(jīng)過(guò)若干條有向邊(弧)能到達(dá)vj。第17頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

路徑的長(zhǎng)度：路徑上邊或有向邊(弧)的數(shù)目稱(chēng)為該路徑的長(zhǎng)度。在一條路徑中，若沒(méi)有重復(fù)相同的頂點(diǎn)，該路徑稱(chēng)為簡(jiǎn)單路徑；第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱(chēng)為回路(環(huán))；在一個(gè)回路中，若除第一個(gè)與最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱(chēng)為簡(jiǎn)單回路(簡(jiǎn)單環(huán))。第18頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月連通圖、圖的連通分量：對(duì)無(wú)向圖G=(V，E)，若

vi，vj

V，又稱(chēng)頂點(diǎn)vi到vj有路徑

，即vi和vj是連通的，則稱(chēng)圖G是連通圖，否則稱(chēng)為非連通圖。若G是非連通圖，則極大的連通子圖稱(chēng)為G的連通分量。 例如圖7.1(b)中的G2就是一個(gè)連通圖。再例如圖7.3所示。P159V1V2V5V4V3G2第19頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

對(duì)有向圖G=(V，E)，若

vi，vj

V，都有以vi為起點(diǎn)，vj

為終點(diǎn)以及以vj為起點(diǎn)，vi為終點(diǎn)的有向路徑，稱(chēng)圖G是強(qiáng)連通圖，否則稱(chēng)為非強(qiáng)連通圖。若G是非強(qiáng)連通圖，則極大的強(qiáng)連通子圖稱(chēng)為G的強(qiáng)連通分量?！皹O大”的含義：指的是對(duì)子圖再增加圖G中的其它頂點(diǎn)，子圖就不再連通。例如圖7.1(a)。V1V3V2V4(G1)V1V3V2V4強(qiáng)連通分量第20頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月生成樹(shù)、生成森林：一個(gè)連通圖(無(wú)向圖)的生成樹(shù)是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)和只有足以構(gòu)成一棵樹(shù)的n-1條邊，稱(chēng)為圖的生成樹(shù)。如圖7.5所示。

v1v3v2v4 圖7-5生成樹(shù)第21頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月 關(guān)于無(wú)向圖的生成樹(shù)的幾個(gè)結(jié)論：◆一棵有n個(gè)頂點(diǎn)的生成樹(shù)有且僅有n-1條邊；◆

如果一個(gè)圖有n個(gè)頂點(diǎn)和小于n-1條邊，則是非連通圖；◆

如果多于n-1條邊，則一定有環(huán)；◆

有n-1條邊的圖不一定是生成樹(shù)。v1v3v2v4 圖7-5生成樹(shù)第22頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月 如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則是一棵有向樹(shù)，如圖7-3所示。 有向圖的生成森林是這樣一個(gè)子圖，由若干棵有向樹(shù)組成，含有圖中全部頂點(diǎn)。網(wǎng)：每個(gè)邊(或弧)都附加一個(gè)權(quán)值的圖，稱(chēng)為帶權(quán)圖。帶權(quán)的連通圖(包括弱連通的有向圖)稱(chēng)為網(wǎng)或網(wǎng)絡(luò)。如圖7-4所示。圖7-3有向圖及其生成森林abcdedce(a)有向圖(b)生成森林acbcb354126abcde3圖7-4帶權(quán)有向圖第23頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月7.1.2圖的抽象數(shù)據(jù)類(lèi)型定義圖的抽象數(shù)據(jù)類(lèi)型定義如下：ADTGraph{數(shù)據(jù)對(duì)象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>的信息}第24頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月基本操作P：CreateGraph(&G,V,VR)：圖的創(chuàng)建操作。初始條件：無(wú)。操作結(jié)果：按V和VR的定義構(gòu)造樹(shù)G。GetVex(G,v)：求圖中的頂點(diǎn)v的值。初始條件：圖G存在，v是圖中的一個(gè)頂點(diǎn)。操作結(jié)果：返回v的值。第25頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月LocateVex(G,u);初始條件：圖G存在，u和G中頂點(diǎn)有相同特征。操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中“位置”；否則返回其它信息PutVex(&G,v,value);

初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：

對(duì)v賦值value。}ADTGraph詳見(jiàn)p156~157。第26頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月習(xí)題七⑴分析并回答下列問(wèn)題：①圖中頂點(diǎn)的度之和與邊數(shù)之和的關(guān)系?②有向圖中頂點(diǎn)的入度之和與出度之和的關(guān)