圖的定義與存儲(chǔ)結(jié)構(gòu)

圖的定義與存儲(chǔ)結(jié)構(gòu)第一頁(yè)，共二十五頁(yè)，編輯于2023年，星期二基本概念G=(V,E)V是頂點(diǎn)集，E是頂點(diǎn)間二元關(guān)系的集合。與樹(shù)的區(qū)別：①樹(shù)有特殊的根結(jié)點(diǎn)；②樹(shù)的結(jié)點(diǎn)和關(guān)系能分成互不相交的若干子集第二頁(yè)，共二十五頁(yè)，編輯于2023年，星期二無(wú)向圖有向圖邊：二元關(guān)系是無(wú)序的。?。憾P(guān)系是有序的。(vi,vj)：vi,vj互為鄰接點(diǎn)

<vi,vj>：弧頭vj、弧尾vi

G1=(V1,E1)V1={v1,v2,v3,v4}E1={(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}G2=(V2,E2)V2={v1,v2,v3,v4}E2={<v1,v2>,<v2,v1>,<v2,v3>,<v4,v3>}第三頁(yè)，共二十五頁(yè)，編輯于2023年，星期二不予討論的圖:(總能轉(zhuǎn)換為簡(jiǎn)單圖)

基本操作對(duì)整體的操作(遍歷)深度遍歷DFSTraverse、廣度遍歷BFSTraverse對(duì)頂點(diǎn)的操作InsertVex、DeleteVex、GetVex、SetVex對(duì)弧/邊的操作InsertArc、DeleteArc、GetArc、SetArc第四頁(yè)，共二十五頁(yè)，編輯于2023年，星期二常見(jiàn)應(yīng)用①信息的組織：家庭照片管理……②運(yùn)輸問(wèn)題：最短路徑問(wèn)題、最優(yōu)乘車路線問(wèn)題……③網(wǎng)絡(luò)規(guī)劃：小區(qū)設(shè)店問(wèn)題、區(qū)域連通的規(guī)劃問(wèn)題……④進(jìn)度組織：工程進(jìn)度管理……第五頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖的分類存儲(chǔ)結(jié)構(gòu)的選擇圖的分解無(wú)向完全圖邊數(shù)：n*(n-1)/2有向完全圖弧數(shù)：n*(n-1)稀疏圖邊數(shù)≈頂點(diǎn)數(shù)稠密圖邊數(shù)≈頂點(diǎn)數(shù)2帶權(quán)圖邊或頂點(diǎn)帶權(quán)值子圖V(B)∈V(A)，E(B)∈E(A)，稱圖B是圖A的子圖54613241510215203041010第六頁(yè)，共二十五頁(yè)，編輯于2023年，星期二頂點(diǎn)的參數(shù)度無(wú)向圖中，依附于某頂點(diǎn)的邊數(shù)出度有向圖中，以某頂點(diǎn)為弧尾的弧數(shù)入度有向圖中，以某頂點(diǎn)為弧頭的弧數(shù)度的應(yīng)用：以下哪個(gè)圖能夠一筆畫(huà)完成？為什么？一筆畫(huà)問(wèn)題的本質(zhì)：圖結(jié)構(gòu)中的邊遍歷問(wèn)題。應(yīng)用領(lǐng)域：車間/廠房布置、行走路線的安排、交通設(shè)計(jì)…第七頁(yè)，共二十五頁(yè)，編輯于2023年，星期二有關(guān)路徑著眼點(diǎn)：頂點(diǎn)間的聯(lián)系頂點(diǎn)間路徑Vi,……,Vj頂點(diǎn)間連通若從Vi到Vj有路徑，稱Vi到Vj是連通的路徑長(zhǎng)度路徑上邊/弧的數(shù)目。簡(jiǎn)單路徑路徑中所有頂點(diǎn)各不相同。回路路徑中，起點(diǎn)和終點(diǎn)是同一頂點(diǎn)。簡(jiǎn)單回路除起點(diǎn)和終點(diǎn)外，其余頂點(diǎn)各不相同第八頁(yè)，共二十五頁(yè)，編輯于2023年，星期二有關(guān)連通著眼點(diǎn)：將不連通圖簡(jiǎn)化為連通圖連通圖無(wú)向圖中,任意二個(gè)頂點(diǎn)之間是連通的無(wú)向圖的連通分量無(wú)向圖的極大連通子圖。強(qiáng)連通圖有向圖中,任意二個(gè)頂點(diǎn)之間存在來(lái)往路徑。有向圖的強(qiáng)連通分量有向圖的極大強(qiáng)連通子圖。

V0

V1

V2

V3非強(qiáng)連通圖

V0

V1

V2

V3有兩個(gè)強(qiáng)連通分量第九頁(yè)，共二十五頁(yè)，編輯于2023年，星期二生成樹(shù)著眼點(diǎn)：將圖簡(jiǎn)化為樹(shù)無(wú)向圖生成樹(shù)連通無(wú)向圖中，n個(gè)頂點(diǎn)和n-1條邊，構(gòu)成的連通子圖。（原連通圖的極小連通子圖）生成森林不連通的無(wú)向圖中，各連通分量的生成樹(shù)的集合。有向圖生成樹(shù)強(qiáng)連通有向圖中，n個(gè)頂點(diǎn)和n-1條弧，構(gòu)成的單向連通子圖(vi、vj間存在一條路徑)一個(gè)頂點(diǎn)入度為０，其余頂點(diǎn)入度為１。生成森林非強(qiáng)連通的有向圖中，各強(qiáng)連通分量的生成樹(shù)的集合。第十頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)至少要保存兩類信息：

1)頂點(diǎn)的數(shù)據(jù)2)頂點(diǎn)間的關(guān)系（邊或?。?)權(quán)的信息（可以沒(méi)有）

如何表示頂點(diǎn)間的關(guān)系？

V0

V4

V3

V1

V2

V0

V1

V2

V3圖的抽象數(shù)據(jù)類型的定義（自學(xué)）第十一頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖的數(shù)組表示法在數(shù)組表示法中，頂點(diǎn)存儲(chǔ)在連續(xù)的存儲(chǔ)空間（數(shù)組）中，用鄰接矩陣表示頂點(diǎn)間的關(guān)系。#defineMaxVnum50typedefVertexTypeVexs[MaxVnum];

typedefdoubleAdjMatrix[MaxVnum][MaxVnum];

typedefstruct{

intvexnum,arcnum;

//圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)

Vexsvexs;//頂點(diǎn)數(shù)組

AdjMatrixarcs;

//鄰接矩陣}Graph;arcs[i][j]=1頂點(diǎn)vi與vj間有邊(弧)0頂點(diǎn)vi與vj間無(wú)邊(弧)第十二頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖的數(shù)組表示法01010010101011010001100011000000001000

V0

V4

V3

V1

V2

V0

V1

V2

V3GraphG1;G1.arcs=G1.vexnum=5；G1.arcnum=6;G1.vexs={V0,V1,V2,V3,V4};GraphG2;G2.arcs=G2.vexnum=4；G2.arcnum=4;G2.vexs={V0,V1,V2,V3};第十三頁(yè)，共二十五頁(yè)，編輯于2023年，星期二1）無(wú)向圖的鄰接矩陣是對(duì)稱矩陣，有向圖的鄰接矩陣不一定是對(duì)稱的；2）頂點(diǎn)v的度：等于二維數(shù)組對(duì)應(yīng)行（或列）中值為1的元素個(gè)數(shù)；頂點(diǎn)v的出度：等于二維數(shù)組對(duì)應(yīng)行中值為1的元素個(gè)數(shù)；頂點(diǎn)v的入度：等于二維數(shù)組對(duì)應(yīng)列中值為1的元素個(gè)數(shù)；3）判斷兩頂點(diǎn)v、u是否為鄰接點(diǎn)：只需判二維數(shù)組對(duì)應(yīng)分量是否為14）頂點(diǎn)不變，在圖中增加、刪除邊：只需對(duì)二維數(shù)組對(duì)應(yīng)分量賦值1或清0；5）設(shè)圖G的頂點(diǎn)數(shù)為n,則G占用的存儲(chǔ)空間為：n+n2；圖的存儲(chǔ)空間占用量只與它的頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān)，適用于邊稠密的圖。

數(shù)組表示法的特點(diǎn)第十四頁(yè)，共二十五頁(yè)，編輯于2023年，星期二網(wǎng)的數(shù)組表示法8273496221V32V2V4V1V6V5∞8∞7498∞21∞∞∞2∞3∞2713∞∞24∞2∞∞69∞226∞

123456123456arcs[i][j]=權(quán)值頂點(diǎn)vi與vj間有邊(弧)∞頂點(diǎn)vi與vj間無(wú)邊(弧)第十五頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖的鄰接表存儲(chǔ)結(jié)構(gòu)例

V0

V4

V3

V1

V2下標(biāo)v01v1v2v3v43∧024∧134∧02∧12∧01234無(wú)向圖的鄰接表頂點(diǎn)：順序結(jié)構(gòu)關(guān)聯(lián)同一頂點(diǎn)的邊：用線性鏈表存儲(chǔ)該結(jié)點(diǎn)表示邊（V0,V1）,其中1是V1在一維數(shù)組中的下標(biāo)頂點(diǎn)數(shù)據(jù)指向第一個(gè)鄰接頂點(diǎn)的指針數(shù)組元素結(jié)構(gòu)無(wú)向圖的鄰接表第十六頁(yè)，共二十五頁(yè)，編輯于2023年，星期二下標(biāo)v01v1∧v2v32∧3∧0∧0123例

V0

V1

V2

V3例

V0

V1

V2

V3下標(biāo)v0v1v2v33∧0∧2∧01230∧有向圖的鄰接表頂點(diǎn)：順序結(jié)構(gòu)以同一頂點(diǎn)為起點(diǎn)的?。河镁€性鏈表存儲(chǔ)（出邊表）有向圖的逆鄰接表以同一頂點(diǎn)為終點(diǎn)的弧：用線性鏈表存儲(chǔ)（入邊表）第十七頁(yè)，共二十五頁(yè)，編輯于2023年，星期二網(wǎng)的鄰接表表示8273496221V32V2V4V1V6V5(c)鄰接鏈表12345628546947∧183241∧22526243∧17213362∧146632∧19425632∧V1V2V3V4V5V6頂點(diǎn)：順序結(jié)構(gòu)關(guān)聯(lián)同一頂點(diǎn)的邊：用線性鏈表存儲(chǔ)表頭頂點(diǎn)的鄰接頂點(diǎn)編號(hào)和邊相關(guān)的信息指向下一個(gè)鄰接頂點(diǎn)的指針(a)表結(jié)點(diǎn)結(jié)構(gòu)第十八頁(yè)，共二十五頁(yè)，編輯于2023年，星期二圖的鄰接表表示typedefstruct{VertexTypedata;ArcNode*firstarc;}AVexNode;typedef

AVexNode

AdjList[MaxVnum];

typedefstructArcNode{intadjvex;doubleweight;structArcNode*nextarc;}ArcNode;表頭頂點(diǎn)的鄰接頂點(diǎn)編號(hào)和邊相關(guān)的信息指向下一個(gè)鄰接頂點(diǎn)的指針(a)表結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)數(shù)據(jù)指向第一個(gè)鄰接頂點(diǎn)的指針(b)頭結(jié)點(diǎn)結(jié)構(gòu)typedefstruct{intvexnum,arcnum;AdjListvertices;}AGraph;

第十九頁(yè)，共二十五頁(yè)，編輯于2023年，星期二有向圖的十字鏈表表示將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)得到的鏈表。在十字鏈表中，頂點(diǎn)結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)元素，弧結(jié)點(diǎn)存儲(chǔ)弧及其上的信息。

V0

V1

V2

V3v0v1v2v300123102∧203∧0∧3∧13∧2∧2∧3∧<v0,v1><v0,v2>鄰接鏈表tailvexheadvexhlinktlinkinfo<vi,vj>弧結(jié)點(diǎn)datafirstinfirstout頂點(diǎn)結(jié)點(diǎn)第二十頁(yè)，共二十五頁(yè)，編輯于2023年，星期二有向圖的十字鏈表表示v0v1v2v300123102∧203∧03∧13∧2∧2∧3∧<v0,v1><v0,v2>逆鄰接鏈表

V0

V1

V2

V3將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)得到的鏈表。在十字鏈表中，頂點(diǎn)結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)元素，弧結(jié)點(diǎn)存儲(chǔ)弧及其上的信息。第二十一頁(yè)，共二十五頁(yè)，編輯于2023年，星期二有向圖的十字鏈表表示v0v1v2v300123102∧203∧0∧3∧13∧2∧2∧3∧<v0,v1><v0,v2>十字鏈表

V0

V1

V2

V3將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)得到的鏈表。在十字鏈表中，頂點(diǎn)結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)元素，弧結(jié)點(diǎn)存儲(chǔ)弧及其上的信息。第二十二頁(yè)，共二十五頁(yè)，編輯于2023年，星期二無(wú)向圖的鄰接多重表表示無(wú)向圖的鄰接多重表表示中，每條邊只表示一次。v0v1v2v30123010∧3∧（v0,v1）（v0,v3）

V0

V4

V3

V1

V221v342341∧∧42∧markivexilinkjvexjlink(vi,vj)第二十三頁(yè)，共二十五頁(yè)，編