數(shù)據(jù)結(jié)構(gòu)第七章節(jié)圖

數(shù)據(jù)結(jié)構(gòu)第7章圖主要內(nèi)容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最短路徑7.1圖的定義和術(shù)語(yǔ)圖(Graph)——圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點(diǎn)的非空有限集

E(G)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)蛴行驅(qū)?。有向圖——有向圖G是由兩個(gè)集合V(G)和E(G)組成的

其中：V(G)是頂點(diǎn)的非空有限集

E(G)是有向邊（也稱(chēng)弧）的有限集合，弧是頂點(diǎn)的有序?qū)Γ洖?lt;v,w>，v,w是頂點(diǎn)，v為弧尾，w為弧頭無(wú)向圖——無(wú)向圖G是由兩個(gè)集合V(G)和E(G)組成的

其中：V(G)是頂點(diǎn)的非空有限集

E(G)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)?，記為（v,w）或（w,v)，并且（v,w)=(w,v)

(u,v)<u,v>V=VertexE=Edge7.1圖的定義和術(shù)語(yǔ)例245136G1有向圖G1=（V，E）中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例157324G26無(wú)向圖G2=（V，E）中：V(G2)={1,2,3,4,5,6,7}E(G2)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}圖的示例7.1圖的定義和術(shù)語(yǔ)有向完全圖——有n(n-1)條弧的n個(gè)頂點(diǎn)的有向圖無(wú)向完全圖——有n(n-1)/2條邊的n個(gè)頂點(diǎn)的無(wú)向圖稀疏圖--若邊或弧的個(gè)數(shù)e<nlogn，則稱(chēng)作稀疏圖，否則成稠密圖。權(quán)—把圖的邊或弧賦予一個(gè)有意義的數(shù)，此數(shù)叫權(quán)帶權(quán)圖-網(wǎng)—弧或邊帶權(quán)的圖分別稱(chēng)作有向網(wǎng)或無(wú)向網(wǎng)。子圖——如果圖G(V,E)和圖G‘(V’,E‘),滿(mǎn)足：

V’V

且E’E，則稱(chēng)G‘為G的子圖鄰接點(diǎn)—若無(wú)向圖G中存在（V,W）,則稱(chēng)V,W互為鄰接點(diǎn)；邊（V，W）和頂點(diǎn)V,W相關(guān)聯(lián)。頂點(diǎn)的度無(wú)向圖中，頂點(diǎn)的度為與該頂點(diǎn)相連的邊數(shù)有向圖中，頂點(diǎn)的度分成入度與出度入度：以該頂點(diǎn)為弧頭的弧的數(shù)目出度：以該頂點(diǎn)為弧尾的弧的數(shù)目7.1圖的定義和術(shù)語(yǔ)證明：①完全有向圖有n(n-1)條邊。證明：若是完全有向圖，則頂點(diǎn)1必與所有其他頂點(diǎn)各有2條連線(xiàn)，即有2(n-1)條邊，頂點(diǎn)2有2(n-2)條邊，…，頂點(diǎn)n-1有2條邊,頂點(diǎn)n有0條邊.總邊數(shù)＝2(n-1＋n-2＋…＋1＋0)=2(n-1+0)n/2=n(n-1)②完全無(wú)向圖有n(n-1)/2條邊。證明：若是完全無(wú)向圖，則頂點(diǎn)1必與所有其他頂點(diǎn)各有1條連線(xiàn)，即有n-1條邊，頂點(diǎn)2有n-2條邊，…，頂點(diǎn)n-1有1條邊,頂點(diǎn)n有0條邊.總邊數(shù)＝n-1＋n-2＋…＋1＋0=（n-1+0)n/2=n(n-1)/27.1圖的定義和術(shù)語(yǔ)例213213有向完全圖無(wú)向完全圖例245136G1頂點(diǎn)2入度：1出度：3頂點(diǎn)4入度：1出度：0例157324G26頂點(diǎn)5的度：3頂點(diǎn)2的度：4ABECF1597211132有向網(wǎng)（弧帶權(quán)值）有向圖頂點(diǎn)的度(TD)=出度(OD)+入度(ID)356例245136圖G與子圖G’G=（V，E）G’=（V’，E’）7.1圖的定義和術(shù)語(yǔ)無(wú)向圖無(wú)向圖(樹(shù))有向圖有向圖n(n-1)/2條邊n(n-1)條邊G1的頂點(diǎn)集合為V(G1)={0,1,2,3}邊集合為E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}完全圖完全圖

圖的練習(xí)：判斷下列4種圖形各屬什么類(lèi)型？7.1圖的定義和術(shù)語(yǔ)簡(jiǎn)單路徑：路徑上各頂點(diǎn)v1,v2,...,vm

均不互相重復(fù)?；芈罚喝袈窂缴系谝粋€(gè)頂點(diǎn)v1

與最后一個(gè)頂點(diǎn)vm

重合，則稱(chēng)這樣的路徑為回路或環(huán)。路徑：在圖G＝(V,E)中,若從頂點(diǎn)

vi出發(fā),沿一些邊經(jīng)過(guò)一些頂點(diǎn)

vp1,

vp2,…,

vpm，到達(dá)頂點(diǎn)vj。則稱(chēng)頂點(diǎn)序列

(vivp1vp2...vpmvj)

為從頂點(diǎn)vi到頂點(diǎn)

vj的路徑。它經(jīng)過(guò)的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)當(dāng)是屬于E的邊。路徑長(zhǎng)度：非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)；帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。簡(jiǎn)單回路：圖的頂點(diǎn)序列中，除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫簡(jiǎn)單回路。7.1圖的定義和術(shù)語(yǔ)例157324G26例245136G1路徑1→3：1,2,3

|（1，2，3，5，6，3

）路徑長(zhǎng)度：2(5)簡(jiǎn)單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡(jiǎn)單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長(zhǎng)度：7簡(jiǎn)單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡(jiǎn)單回路：1，2，3，17.1圖的定義和術(shù)語(yǔ)連通圖例3231強(qiáng)連通圖456例2例1245136

在無(wú)向圖中,若從頂點(diǎn)vi到頂點(diǎn)vj有路徑,則稱(chēng)頂點(diǎn)vi與vj是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的,則稱(chēng)此圖是連通圖。

非連通圖的極大連通子圖叫做連通分量。

在有向圖中,

若對(duì)于每一對(duì)頂點(diǎn)vi和vj,

都存在一條從vi到vj和從vj到vi的路徑,則稱(chēng)此圖是強(qiáng)連通圖。

非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。77.1圖的定義和術(shù)語(yǔ)

假設(shè)一個(gè)（無(wú)向）連通圖有n個(gè)頂點(diǎn)和e條邊，其中n-1條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱(chēng)該極小連通子圖為此連通圖的生成樹(shù)。對(duì)非連通圖，則稱(chēng)由各個(gè)連通分量的生成樹(shù)的集合為此非連通圖的生成森林。BACDFE生成樹(shù)7.1圖的定義和術(shù)語(yǔ)圖的基本操作結(jié)構(gòu)的建立和銷(xiāo)毀插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪(fǎng)問(wèn)操作遍歷插入和刪除弧7.1圖的定義和術(shù)語(yǔ)圖的基本操作CreatGraph(&G,V,VR)://按定義(V,VR)構(gòu)造圖DestroyGraph(&G)://銷(xiāo)毀圖結(jié)構(gòu)的建立和銷(xiāo)毀7.1圖的定義和術(shù)語(yǔ)圖的基本操作對(duì)頂點(diǎn)的訪(fǎng)問(wèn)操作LocateVex(G,u);

//若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在

//圖中“位置”;否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對(duì)v賦值value。7.1圖的定義和術(shù)語(yǔ)圖的基本操作對(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)，則//返回“空”。7.1圖的定義和術(shù)語(yǔ)圖的基本操作插入或刪除頂點(diǎn)InsertVex(&G,v);

//在圖G中增添新頂點(diǎn)v。DeleteVex(&G,v);//刪除G中頂點(diǎn)v及其相關(guān)的弧。7.1圖的定義和術(shù)語(yǔ)圖的基本操作插入和刪除弧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)。7.1圖的定義和術(shù)語(yǔ)圖的基本操作遍歷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一次且僅一次。7.2圖的存儲(chǔ)結(jié)構(gòu)一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示二、圖的鄰接表存儲(chǔ)表示三、有向圖的十字鏈表存儲(chǔ)表示四、無(wú)向圖的鄰接多重表存儲(chǔ)表示7.2圖的存儲(chǔ)結(jié)構(gòu)圖的數(shù)組存儲(chǔ)表示用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)信息和頂點(diǎn)之間的關(guān)系信息(鄰接矩陣—表示頂點(diǎn)間相鄰關(guān)系的矩陣)定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A（二維數(shù)組）是具有以下性質(zhì)的n階方陣：例G12413例15324G27.2圖的存儲(chǔ)結(jié)構(gòu)圖的數(shù)組存儲(chǔ)表示

鄰接矩陣特點(diǎn)：無(wú)向圖的鄰接矩陣對(duì)稱(chēng)，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n(n+1)/2有向圖鄰接矩陣不一定對(duì)稱(chēng)；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2無(wú)向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和(第i行非0元素1的個(gè)數(shù))

有向圖中，頂點(diǎn)Vi的出度是A中第i行元素之和頂點(diǎn)Vi的入度是A中第i列元素之和例G12413例15324G27.2圖的存儲(chǔ)結(jié)構(gòu)圖的數(shù)組存儲(chǔ)表示例1452375318642網(wǎng)的鄰接矩陣示意圖網(wǎng)的鄰接矩陣可定義為：∞反之

容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等等。

n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。對(duì)稀疏圖而言尤其浪費(fèi)空間。鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺點(diǎn)：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];#defineINFINITY INT_MAX//定義無(wú)窮大∞#defineMAX_VERTEX_NUM 20

//定義圖的類(lèi)型{有向圖,有向網(wǎng),無(wú)向圖,無(wú)向網(wǎng)}typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstruct{//圖的定義

VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)數(shù)組

AdjMatrixarcs;//鄰接矩陣，可設(shè)二維

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

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

}MGraph;7.2圖的存儲(chǔ)結(jié)構(gòu)圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示實(shí)現(xiàn)7.2圖的存儲(chǔ)結(jié)構(gòu)圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示實(shí)現(xiàn)例G12413例15324G2G1.vexs={1，2，3，4}；G1.arcs=G1.vexnum=4；G1.arcnum=4；G1.kind=DG；G2.vexs={1，2，3，4，5}；G2.arcs=G2.vexnum=5；G2.arcnum=6；G2.kind=UDG；7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示表頭結(jié)點(diǎn)結(jié)構(gòu):數(shù)據(jù)域（data）用于存儲(chǔ)頂點(diǎn)的名或其它有關(guān)信息；

鏈域（firstarc）用于指向鏈表中第一個(gè)頂點(diǎn)（即與頂點(diǎn)

vi鄰接的第一個(gè)鄰接點(diǎn)）邊表結(jié)點(diǎn)結(jié)構(gòu)：adjvex與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置

info存儲(chǔ)和邊相關(guān)的信息(若無(wú)，則置空NULL)

nextarc指向下一條邊的結(jié)點(diǎn)的指針表頭結(jié)點(diǎn)弧結(jié)點(diǎn)

datafirstarcadjvexinfonextarc實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的?。煌瑫r(shí)為每一個(gè)單鏈表附設(shè)一個(gè)表頭結(jié)點(diǎn)，并將所有的表頭結(jié)點(diǎn)順序存儲(chǔ)（數(shù)組），以便隨機(jī)訪(fǎng)問(wèn)任一頂點(diǎn)的鏈表。typedefstructArcNode//弧結(jié)點(diǎn){intadjvex;

//鄰接點(diǎn)域，存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置

structnode*nextarc;

//鏈域，指示依附于vi的下一條邊或弧的結(jié)點(diǎn)，

//VRTypeweight;

InfoType*info;//定義與弧相關(guān)的權(quán)值，無(wú)權(quán)則為0

}ArcNode;

//定義指向該弧相關(guān)信息的指針

typedefstructVNode//表頭結(jié)點(diǎn){charvexdata;//存放頂點(diǎn)信息

structArcNode*firstarc;//指示第一個(gè)鄰接點(diǎn)}VNode，AdjList[MAX_VERTEX_NUM];vexdatafirstarctypedefstruct{

//圖的結(jié)構(gòu)定義

AdjList

vertices;//頂點(diǎn)向量

intvexnum,arcnum;GraphKindkind;//圖的種類(lèi)標(biāo)志

}MGraph;adjvexnextarcWeightinfo7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示例G1bdac例aecbdG21234acdbvexdatafirstarc3241^^^^adjvexnextarc1234acdbvexdatafirstarc421

2^^^adjvexnextarc5e435^

15323^提示：在無(wú)向圖，每一個(gè)邊結(jié)點(diǎn)在圖的單鏈表中出現(xiàn)兩次，故無(wú)向圖中若有n個(gè)頂點(diǎn)和e條邊，則需要存儲(chǔ)空間為：n+2e7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示鄰接表特點(diǎn)無(wú)向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)有向圖中頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)（以vi為弧頭）。為此需遍歷整個(gè)鄰接表。一種解決的方法是逆鄰接表法

一種解決的方法是逆鄰接表法，我們可以對(duì)每一頂點(diǎn)vi再建立一個(gè)逆鄰接表，即對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)所有以頂點(diǎn)vi為弧頭的弧的表，如圖所示。

圖G1的鄰接表和逆鄰接表表示法

例G1bdac1234acdbvexdatafirstarc41^1^^3^adjvex

nextarc1234acdbvexdatafirstarc2341^^^^adjvexnextarc7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示討論：鄰接表與鄰接矩陣有什么異同之處？聯(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)。e隨n的改變而變化--函數(shù)關(guān)系3.用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（e<<n2)7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示

圖的鄰接表是應(yīng)用較多的一種存儲(chǔ)結(jié)構(gòu)。從鄰接表的結(jié)構(gòu)定義可見(jiàn)，建立鄰接表的主要操作是在鏈表中插入一個(gè)結(jié)點(diǎn)，以下是輸入無(wú)向圖的頂點(diǎn)和邊建立鄰接表的算法步驟。BCAFE

D0

A

4

11

B54

02C533D524

E

105F320頭插法vexdatafirstarcadjvexnextarc建立有（無(wú)）向圖的鄰接表7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示建立有（無(wú)）向圖的鄰接表

建立鄰接表的主要操作是在鏈表中插入一個(gè)結(jié)點(diǎn)，以下是輸入有向圖的頂點(diǎn)和弧建立鄰接表的算法。依次輸入的數(shù)據(jù)為：

1.

57DG2.

ABCDE3.

ABAEBCCDDADBEC

ABECD142301201234ABCDE尾插法7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示voidCreateGraph(MGraph&G){//生成圖G的存儲(chǔ)結(jié)構(gòu)-鄰接表

cin>>G.vexnum>>G.arcnum>>G.kind;//輸入頂點(diǎn)數(shù)、邊數(shù)和圖類(lèi)：1

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

{

//構(gòu)造頂點(diǎn)數(shù)組：2

cin>>G.vertices[i].data;

//輸入頂點(diǎn)

G.vertices[i].firstarc=NULL;}//for，初始化鏈表頭指針為"空"

for(k=0;k<G.arcnum;++k)//輸入各邊并構(gòu)造鄰接表：3{cin>>sv>>tv;

//輸入一條邊（弧）的始點(diǎn)和終點(diǎn)

i=LocateVex(G,sv);j=LocateVex(G,tv);//確定sv和tv//在G中位置，即頂點(diǎn)在G.vertices中的序號(hào)pi=newArcNode;

if(!pi)exit(-1);

//存儲(chǔ)分配失敗

pi->adjvex=j;

//對(duì)弧結(jié)點(diǎn)賦鄰接點(diǎn)"位置“

if(G.kind==DN||G.kind==DG)

cin>>w>>p;//有向圖輸入權(quán)值和其它信息存儲(chǔ)地址

else

{w=0;p=NULL;}

pi->weight=w;pi->info=p;

pi->nextarc=G.vertices[i].firstarc;

//頭插法，將tv結(jié)點(diǎn)插入到第i個(gè)單鏈表中G.vertices[i].firstarc=pi;

//插入鏈表G.vertices[i]

vexdatafirstarcadjvexnextarc7.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)表示if(G.kind==UDG||G.kind==UDN){//對(duì)無(wú)向圖或無(wú)向網(wǎng)尚需建立tv的鄰接點(diǎn)：4

pj=newArcNode;

if(!pi)exit(-1);

//存儲(chǔ)分配失敗

pj->adjvex=i;

//對(duì)邊結(jié)點(diǎn)賦鄰接點(diǎn)“位置”

pj->weight=w;pj->info=p;

//頭插法，將sv結(jié)點(diǎn)插入到第j個(gè)單鏈表中,插入鏈表G.vertices[j]pj->nextarc=G.vertices[j].firstarc;

G.vertices[j].firstarc=pj;}//if}//for}//CreateGraph

雖然在有向圖的鄰接表和逆鄰接表中分別可以找到從頂點(diǎn)出發(fā)的弧和指向頂點(diǎn)的弧，但對(duì)于同一個(gè)有向圖需要用兩個(gè)結(jié)構(gòu)來(lái)表示它畢竟不方便，因此當(dāng)應(yīng)用問(wèn)題中同時(shí)需要對(duì)這兩種弧進(jìn)行處理時(shí)就需要采用十字鏈表來(lái)表示有向圖。十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，目的是將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個(gè)結(jié)點(diǎn)表示，由于在鄰接表和逆鄰接表中的頂點(diǎn)數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。

是鄰接表和逆鄰接表兩者的結(jié)合：對(duì)于有向圖中的每一條弧有一個(gè)弧結(jié)點(diǎn)，每一個(gè)頂點(diǎn)有一個(gè)頂點(diǎn)結(jié)點(diǎn)。7.2圖的存儲(chǔ)結(jié)構(gòu)有向圖的十字鏈表存儲(chǔ)表示7.2圖的存儲(chǔ)結(jié)構(gòu)有向圖的十字鏈表存儲(chǔ)表示是有向圖的鄰接表和逆鄰接表組合7.2圖的存儲(chǔ)結(jié)構(gòu)有向圖的十字鏈表存儲(chǔ)表示typedefstructArcNode{inttailvex,headvex;//弧尾、弧頭在表頭數(shù)組中位置

structArcNode*hlink；//指向弧頭相同的下一條弧

structArcNode*tlink;//指向弧尾相同的下一條弧

InfoType*info;//定義弧的相關(guān)信息，如權(quán)值}ArcNode;typedefstructVexNode{intdata;//存與頂點(diǎn)有關(guān)信息

ArcNode*firstin；//指向以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)

ArcNode*firstout;//指向以該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)}VexNode;datafirstinfirstouttailvexheadvexhlinktlinkinfo弧結(jié)點(diǎn)：頂點(diǎn)結(jié)點(diǎn)：typedefstruct{//圖的定義

VexNodexlist[MAX_VERTEX_NUM];//頂點(diǎn)結(jié)點(diǎn)(表頭向量)intvexnum,arcnum;//有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}OLGraph;7.2圖的存儲(chǔ)結(jié)構(gòu)ABCABC012∧02∧∧0121∧20∧∧有向圖的十字鏈表存儲(chǔ)表示7.2圖的存儲(chǔ)結(jié)構(gòu)無(wú)向圖的鄰接多重表存儲(chǔ)表示

類(lèi)似于有向圖的十字鏈表，若將無(wú)向圖中表示同一條邊的兩個(gè)結(jié)點(diǎn)合在一起，將得到無(wú)向圖的另一種表示方法--鄰接多重表。

7.2圖的存儲(chǔ)結(jié)構(gòu)無(wú)向圖的鄰接多重表存儲(chǔ)表示在鄰接多重表中，每一條邊用一個(gè)結(jié)點(diǎn)表示，邊結(jié)點(diǎn)結(jié)構(gòu)如下：markivex

ilink

jvex

jlinkinfoconstMAX_VERTEX_NUM=20;

typedefemnu{unvisited,visited}VisitIf;typedefstructEdgeNode{

//邊結(jié)點(diǎn)結(jié)構(gòu)定義

VisitIfmark;

//訪(fǎng)問(wèn)標(biāo)記

intivex,jvex;

//該邊依附的兩個(gè)頂點(diǎn)（vi，vj）在圖中的位置

structEdgeNode*ilink,*jlink;//分別指向依附這兩個(gè)頂點(diǎn)的下一條邊

VRTypeweight;

//與弧相關(guān)的權(quán)值，無(wú)權(quán)則為0

InfoType*info;

//與該邊相關(guān)信息的指針

};datafirstedge

頂點(diǎn)結(jié)點(diǎn)：typedefstruct{

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

VertexTypedata;

EdgeNode*firstedge;

//指向第一條依附該頂點(diǎn)的邊

}VexNode;typedefstruct{

//多重鏈表結(jié)構(gòu)定義

VexNodeadjmulist[MAX_VERTEX_NUM];

intvexnum,edgenum;

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

GraphKindkind;

//圖的種類(lèi)標(biāo)志

}AMLGraph;7.2圖的存儲(chǔ)結(jié)構(gòu)無(wú)向圖的鄰接多重表存儲(chǔ)表示BCAFE

D

例如，無(wú)向圖的鄰接多重表如下所示(忽略相關(guān)信息指針）7.2圖的存儲(chǔ)結(jié)構(gòu)

各種存儲(chǔ)結(jié)構(gòu)的適用類(lèi)型數(shù)組(鄰接矩陣)：有向圖和無(wú)向圖鄰接表（逆鄰接表）：有向圖和無(wú)向圖十字鏈表：有向圖鄰接多重表：無(wú)向圖7.3圖的遍歷

從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪(fǎng)遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次的過(guò)程。圖的遍歷（TraversingGraph）:V1V2V4V5V3V7V6V8例提示：前面學(xué)習(xí)過(guò)樹(shù)的遍歷有遞歸遍歷（前序、中序和后序）和非遞歸算法演示提問(wèn)：樹(shù)的遍歷能否用于圖的遍歷？能或不能為什么？不能！因?yàn)閳D有回路，若用樹(shù)的遍歷算法可能導(dǎo)致無(wú)限循環(huán)。為防止循環(huán)，可設(shè)置已訪(fǎng)問(wèn)標(biāo)志。然而，圖中可能有孤立點(diǎn)，若不加修改地使用樹(shù)的遍歷，就可能會(huì)遺漏圖中的一部分頂點(diǎn)。7.3圖的遍歷

為了保證圖中的各頂點(diǎn)在遍歷過(guò)程中訪(fǎng)問(wèn)且僅訪(fǎng)問(wèn)一次，需要為每個(gè)頂點(diǎn)設(shè)一個(gè)訪(fǎng)問(wèn)標(biāo)志，因此我們?yōu)閳D設(shè)置一個(gè)訪(fǎng)問(wèn)標(biāo)志數(shù)組visited［n］:vi未被訪(fǎng)問(wèn):visited[i]值為falsevi被訪(fǎng)問(wèn)過(guò)：visited［i］為true

根據(jù)搜索路徑方向不同：深度優(yōu)先搜索（縱向↓）廣度優(yōu)先搜索（橫向→）遍歷應(yīng)用舉例V1V2V4V5V3V7V6V8例7.3圖的遍歷

深度優(yōu)先搜索(Depth-FirstSearch—DFS)是指按照深度方向搜索,它類(lèi)似于樹(shù)的先根遍歷,是樹(shù)的先根遍歷的推廣。深度優(yōu)先搜索連通子圖的基本思想是：假設(shè)圖G初態(tài)為所有頂點(diǎn)未被訪(fǎng)問(wèn)（visited[i]=false），從G中任選一頂點(diǎn)vi

：

⑴、從該頂點(diǎn)vi出發(fā),首先訪(fǎng)問(wèn)vi,,置visited[vi]=true;

⑵、然后依次搜索vi的每一個(gè)鄰接點(diǎn)vj

；⑶、若vj未被訪(fǎng)問(wèn)過(guò)，則以vj為新的初始出發(fā)點(diǎn)，重復(fù)⑴若vj已被訪(fǎng)問(wèn)過(guò)，則返回到vi另一個(gè)鄰接點(diǎn)，重復(fù)⑶

⑷、如果經(jīng)過(guò)⑴、⑵、⑶后,圖中仍有未被訪(fǎng)問(wèn)的頂點(diǎn),再?gòu)闹腥芜x一頂點(diǎn),重復(fù)⑴、⑵、⑶,直至所有頂點(diǎn)都被訪(fǎng)問(wèn)過(guò),遍歷結(jié)束。V1V2V4V5V3V7V6V8例無(wú)向圖深度遍歷：V1V2V4V8V5V3V6V7深度優(yōu)先搜索遍歷圖V1V2V4V5V3V7V6V8例深度遍歷：V11234v1v3v4v2vexdatafirstarc2783^^^adjvexnext5v5641^51282^v6v7v8678736354^^^V3V7V6V2V5V8V4思考題：按圖的存儲(chǔ)結(jié)構(gòu)如何遍歷？思想同算法vi=v11.訪(fǎng)問(wèn)V1。2.求

Vi的鄰接點(diǎn)Vj

。

3.若vj未被訪(fǎng)問(wèn)過(guò)，則以vj為新的初始出發(fā)點(diǎn)，重復(fù)⑴若vj已被訪(fǎng)問(wèn)過(guò)，則返回到vi另一個(gè)鄰接點(diǎn)，重復(fù)⑶7.3圖的遍歷深度優(yōu)先搜索遍歷圖7.3圖的遍歷深度優(yōu)先搜索遍歷圖V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍歷：V1V3V7V6V2V4V8V57.3圖的遍歷深度優(yōu)先搜索遍歷圖從上頁(yè)的遍歷過(guò)程可見(jiàn):1.深度優(yōu)先搜索遍歷連通圖的過(guò)程類(lèi)似于樹(shù)的先根遍歷；解決的辦法是：為每個(gè)頂點(diǎn)v設(shè)立一個(gè)

“訪(fǎng)問(wèn)標(biāo)志visited[v]”。2.如何判別V的鄰接點(diǎn)是否被訪(fǎng)問(wèn)？3.如何求V的鄰接點(diǎn)？解決的辦法是：根據(jù)圖的存儲(chǔ)結(jié)構(gòu)來(lái)確定。對(duì)于鄰接表而言，通過(guò)頂點(diǎn)向量和對(duì)應(yīng)的單鏈表查找鄰接點(diǎn)。7.3圖的遍歷深度優(yōu)先搜索遍歷圖深度優(yōu)先遍歷算法-遞歸算法開(kāi)始訪(fǎng)問(wèn)V0,置標(biāo)志求V0鄰接點(diǎn)有鄰接點(diǎn)w？求下一鄰接點(diǎn)w→V0W訪(fǎng)問(wèn)過(guò)？返回NYNYDFS開(kāi)始標(biāo)志數(shù)組初始化Vi=0Vi訪(fǎng)問(wèn)過(guò)DFSVi=Vi+1Vi<Vexnums結(jié)束NNYYvoidDFS(GraphG,intv){

//從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖G

visited[v]=TRUE;VisitFunc(v);

for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))

//返回V的(相對(duì)于w)下一鄰接點(diǎn)

if(!visited[w])DFS(G,w);

//對(duì)v的尚未訪(fǎng)問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFS}//DFS提示：

對(duì)于連通圖，從任一頂點(diǎn)v出發(fā)，能夠深度優(yōu)先搜索遍歷整個(gè)圖G，訪(fǎng)問(wèn)所有結(jié)點(diǎn)；

而對(duì)于非連通圖，則需從多個(gè)頂點(diǎn)出發(fā)，方可。開(kāi)始訪(fǎng)問(wèn)V0,置標(biāo)志求V0鄰接點(diǎn)有鄰接點(diǎn)W？求下一鄰接點(diǎn)w→V0W訪(fǎng)問(wèn)過(guò)？返回NYNYDFS7.3圖的遍歷深度優(yōu)先搜索遍歷圖7.3圖的遍歷深度優(yōu)先搜索遍歷圖

首先將圖中每個(gè)頂點(diǎn)的訪(fǎng)問(wèn)標(biāo)志設(shè)為FALSE,之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪(fǎng)問(wèn)，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。非連通圖的深度優(yōu)先搜索遍歷abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg訪(fǎng)問(wèn)標(biāo)志:訪(fǎng)問(wèn)次序:例如:0123456787.3圖的遍歷深度優(yōu)先搜索遍歷圖voidDFSTraverse(GraphG,

Status(*Visit)(intv))

{//對(duì)圖G作深度優(yōu)先遍歷。

VisitFunc=Visit;//初始化訪(fǎng)問(wèn)函數(shù)

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪(fǎng)問(wèn)標(biāo)志數(shù)組初始化

for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);

//對(duì)尚未訪(fǎng)問(wèn)的頂點(diǎn)調(diào)用DFS}深度優(yōu)先搜索遍歷非連通圖

G的算法描述開(kāi)始標(biāo)志數(shù)組初始化Vi=0Vi訪(fǎng)問(wèn)過(guò)DFSVi=Vi+1Vi<Vexnums結(jié)束NNYY7.3圖的遍歷深度優(yōu)先搜索遍歷圖DFS算法效率分析:（設(shè)圖中有n個(gè)頂點(diǎn)，e條邊）如果用鄰接矩陣來(lái)表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要從頭掃描該頂點(diǎn)所在行，因此遍歷全部頂點(diǎn)所需的時(shí)間為O(n2)。如果用鄰接表來(lái)表示圖，雖然有2e

個(gè)表結(jié)點(diǎn)，但只需掃描e

個(gè)結(jié)點(diǎn)即可完成遍歷（∵判斷訪(fǎng)問(wèn)標(biāo)志），加上訪(fǎng)問(wèn)

n個(gè)頭結(jié)點(diǎn)的時(shí)間，因此遍歷圖的時(shí)間復(fù)雜度為O(n+e)。結(jié)論：稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷；稀疏圖適于在鄰接表上進(jìn)行深度遍歷。7.3圖的遍歷深度優(yōu)先搜索遍歷圖1.從圖中某頂點(diǎn)v出發(fā)，在訪(fǎng)問(wèn)v之后，2.依次訪(fǎng)問(wèn)v的各個(gè)未曾被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)，3.然后分別從這些鄰接點(diǎn)出發(fā)依次訪(fǎng)問(wèn)它們的鄰接點(diǎn)，并使“先被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪(fǎng)問(wèn)，直至圖中所有已經(jīng)被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪(fǎng)問(wèn)到；4.若圖中尚有頂點(diǎn)未曾被訪(fǎng)問(wèn)，則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，訪(fǎng)問(wèn)該頂點(diǎn)，繼續(xù)過(guò)程2、3,直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。V1V2V4V5V3V7V6V8例無(wú)向圖V1V2V4V5V3V7V6V8例有向圖序列：V1V2V3V4V5V6V7V8序列：V1V2V3V4V6V7V8V57.3圖的遍歷廣度優(yōu)先搜索遍歷圖樹(shù)的層次遍歷的推廣V1V2V4V5V3V7V6V8例廣度遍歷：V11234v1v3v4v2vexdatafirstarc2783^^^adjvexnext5v5641^51282^v6v7v8678736354^^^V3V2V7V6V5V4V8思考題：按圖的存儲(chǔ)結(jié)構(gòu)如何遍歷？鄰接矩陣如何？思想同算法vi=v17.3圖的遍歷廣度優(yōu)先搜索遍歷圖說(shuō)明：

廣度優(yōu)先搜索遍歷圖時(shí)，對(duì)連通圖，從起始點(diǎn)V到其余各頂點(diǎn)必定存在路徑，并且訪(fǎng)問(wèn)頂點(diǎn)的次序是按頂點(diǎn)的路徑長(zhǎng)度遞增進(jìn)行的。

從V1出發(fā)，V1->v2,V1->v3

的路徑長(zhǎng)度為1；

V1->v4,V1->v5,V1->v6,V1->v7

的路徑長(zhǎng)度為2；V1->v8

的路徑長(zhǎng)度為3。V1V2V4V5V3V7V6V8例例如：廣度遍歷序列：V1V2V3V4V5V6V7V87.3圖的遍歷廣度優(yōu)先搜索遍歷圖7.3圖的遍歷廣度優(yōu)先搜索遍歷圖為避免重復(fù)訪(fǎng)問(wèn),需要一個(gè)輔助數(shù)組visited[n]，給被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)加標(biāo)記。為了實(shí)現(xiàn)逐層（按頂點(diǎn)的路徑長(zhǎng)度遞增）訪(fǎng)問(wèn),算法中需使用了一個(gè)隊(duì)列,以記憶正在訪(fǎng)問(wèn)的這一層和下一層的頂點(diǎn),以便于向下一層訪(fǎng)問(wèn)。7.3圖的遍歷廣度優(yōu)先搜索遍歷圖12341342vexdatafirstarc5543^^^adjvexnext551^51143^220123451fr遍歷序列：10123454fr遍歷序列：1401234543fr遍歷序列：143先訪(fǎng)問(wèn)后入隊(duì)1出隊(duì)，依次得到其所有鄰接點(diǎn)，輸出并進(jìn)隊(duì)例1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^22012345432fr遍歷序列：1432012345325fr遍歷序列：143251的鄰接點(diǎn)入隊(duì)完畢，4出隊(duì)，依次得到其所有未被訪(fǎng)問(wèn)的鄰接點(diǎn)，輸出并進(jìn)隊(duì)例142357.3圖的遍歷廣度優(yōu)先搜索遍歷圖01234525fr遍歷序列：143250123455fr遍歷序列/p>

fr遍歷序列：14325例1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^227.3圖的遍歷廣度優(yōu)先搜索遍歷圖開(kāi)始訪(fǎng)問(wèn)V,置標(biāo)志求U鄰接點(diǎn)WW存在嗎U下一鄰接點(diǎn)WW訪(fǎng)問(wèn)過(guò)結(jié)束NYNY初始化隊(duì)列V入隊(duì)隊(duì)列空嗎隊(duì)頭出隊(duì)U訪(fǎng)問(wèn)W,置標(biāo)志W(wǎng)入隊(duì)NaaYBFS開(kāi)始標(biāo)志數(shù)組初始化Vi=0Vi訪(fǎng)問(wèn)過(guò)？BFSVi=Vi+1Vi<Vexnums？結(jié)束NNYY142357.3圖的遍歷廣度優(yōu)先搜索遍歷圖7.3圖的遍歷廣度優(yōu)先搜索遍歷圖

voidBFSTraverse(GraphG,Status(*Visit)(intv)){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//初始化訪(fǎng)問(wèn)標(biāo)志

InitQueue(Q);//置空的輔助隊(duì)列Q

for(v=0;v<G.vexnum;++v)

if(!visited[v])//v尚未訪(fǎng)問(wèn)

{

//調(diào)用BFS()}}//BFSTraverseBFS(

G,v)；開(kāi)始標(biāo)志數(shù)組初始化Vi=0Vi訪(fǎng)問(wèn)過(guò)BFSVi=Vi+1Vi<Vexnums結(jié)束NNYYvoidBFS(GraphG,

intv){visited[v]=TRUE;Visit(v);//訪(fǎng)問(wèn)vEnQueue(Q,v);//v入隊(duì)列while(!QueueEmpty(Q)){

DeQueue(Q,u);//隊(duì)頭元素出隊(duì)并置為u

for(w=FirstAdjVex(G,u);

w!=0;

w=NextAdjVex(G,u,w))

if(!visited[w]){

visited[w]=TRUE;Visit(w);

EnQueue(Q,w);

//訪(fǎng)問(wèn)的頂點(diǎn)w入隊(duì)列

}//if

}//while}開(kāi)始訪(fǎng)問(wèn)V,置標(biāo)志求U鄰接點(diǎn)WW存在嗎U下一鄰接點(diǎn)WW訪(fǎng)問(wèn)過(guò)結(jié)束NYNY初始化隊(duì)列V入隊(duì)隊(duì)列空嗎隊(duì)頭出隊(duì)U訪(fǎng)問(wèn)W,置標(biāo)志W(wǎng)入隊(duì)NaaYBFS7.3圖的遍歷廣度優(yōu)先搜索遍歷圖7.3圖的遍歷廣度優(yōu)先搜索遍歷圖BFS算法效率分析:同DFSDFS與BFS之比較：空間復(fù)雜度相同，都是O(n)(借用了堆?；蜿?duì)列）；時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無(wú)關(guān)。鄰接表存儲(chǔ)圖，則BFS的時(shí)間復(fù)雜度：O(n+e)

鄰接矩陣存儲(chǔ)圖，則BFS的時(shí)間復(fù)雜度：O(n2)。（設(shè)圖中有n個(gè)頂點(diǎn)，e條邊）1.求一條從頂點(diǎn)i到頂點(diǎn)s的

簡(jiǎn)單路徑2.

求兩個(gè)頂點(diǎn)之間的一條路徑長(zhǎng)度最短的路徑7.3圖的遍歷遍歷應(yīng)用舉例7.3圖的遍歷遍歷應(yīng)用舉例1.

求一條從頂點(diǎn)i到頂點(diǎn)s的簡(jiǎn)單路徑

求從頂點(diǎn)b到頂點(diǎn)k的一條簡(jiǎn)單路徑。

從頂點(diǎn)b

出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。例如:

假設(shè)找到的第一個(gè)鄰接點(diǎn)是a，則得到的結(jié)點(diǎn)訪(fǎng)問(wèn)序列為:

b

a

dhc

e

k

fg。

假設(shè)找到的第一個(gè)鄰接點(diǎn)是c，則得到的結(jié)點(diǎn)訪(fǎng)問(wèn)序列為:

b

chdae

k

fg，abchdekfg思考:如何查找此路徑？

遍歷過(guò)程中，檢查是否到終點(diǎn)，是則止，否則繼續(xù)。可能需進(jìn)行若干次試探、回溯7.3圖的遍歷遍歷應(yīng)用舉例1.

從頂點(diǎn)i

到頂點(diǎn)s,若存在路徑，則從頂點(diǎn)

i出發(fā)進(jìn)行深度優(yōu)先搜索，必能搜索到頂點(diǎn)s。2.

遍歷過(guò)程中搜索到的頂點(diǎn)不一定是路徑上的頂點(diǎn)，則將該頂點(diǎn)從路徑中刪去，如搜索路徑為：i,…,h,v’，…

，再?gòu)膆出發(fā)重新探索下一條路經(jīng)。結(jié)論:3.

由它出發(fā)進(jìn)行的深度優(yōu)先遍歷整個(gè)圖，已經(jīng)完成的頂點(diǎn)不是路徑上的頂點(diǎn)，則說(shuō)明不存在路徑（i,…,s）。voidDFSearch(intv,ints,char*PATH){//從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G，求得一條從v到s的簡(jiǎn)單路徑，并記錄在PATH中

visited[v]=TRUE;//訪(fǎng)問(wèn)第v個(gè)頂點(diǎn)，能不被重復(fù)訪(fǎng)問(wèn)

Append(PATH,getVertex(v));

//第v個(gè)頂點(diǎn)加入路徑

//k++；

for(w=FirstAdjVex(G，v);w!=0&&!found;

w=NextAdjVex(G，v，w))

{

if(w==s){found=TRUE;Append(PATH,w);exit(1);}//找到退出

else

if(!visited[w])DFSearch(w,s,PATH);//加入w

}//endfor

if(!found)Delete(PATH，v);

//從路徑上刪除頂點(diǎn)v

}//7.3圖的遍歷遍歷應(yīng)用舉例voidDFSearch(intv,ints,intk,char*PATH){//判斷鄰接表方式存儲(chǔ)的有向圖G的頂點(diǎn)v到s是否存在長(zhǎng)度為k的簡(jiǎn)單路徑，并記錄在PATH中

if(v==s&&k==0)//找到了一條路徑,且長(zhǎng)度符合要求

{found=TRUE;Append(PATH,v);return；}

elseif(k>0){visited[v]=TRUE;//訪(fǎng)問(wèn)第v個(gè)頂點(diǎn)

Append(PATH,getVertex(v));L++；//第v個(gè)頂點(diǎn)加入路徑

for(w=FirstAdjVex(G，v);w!=0&&!found;

w=NextAdjVex(G，v，w))

if(L==k&&w==s){found=TRUE;Append(PATH,w);}//找到退出

else

if(!visited[w])DFSearch(w,s,k-1,PATH);if(!found)Delete(PATH,v);

//從路徑上刪除頂點(diǎn)v

}//求有向圖G的頂點(diǎn)v到s是否存在長(zhǎng)度為k的簡(jiǎn)單路徑7.3圖的遍歷遍歷應(yīng)用舉例2.

求兩個(gè)頂點(diǎn)之間的一條路徑長(zhǎng)度最短的路徑課下思考

若兩個(gè)頂點(diǎn)之間存在多條路徑，則其中必有一條路徑長(zhǎng)度最短的路徑。如何求得這條路徑?7.3圖的遍歷遍歷應(yīng)用舉例7.3圖的遍歷遍歷應(yīng)用舉例abchdekfg因此，求路徑長(zhǎng)度最短的路徑可以基于廣度優(yōu)先搜索遍歷進(jìn)行，但需要修改鏈隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)及其入隊(duì)列和出隊(duì)列的算法。深度優(yōu)先搜索訪(fǎng)問(wèn)頂點(diǎn)的次序取決于圖的存儲(chǔ)結(jié)構(gòu)，而廣度優(yōu)先搜索訪(fǎng)問(wèn)頂點(diǎn)的次序是按“路徑長(zhǎng)度”漸增的次序。7.3圖的遍歷遍歷應(yīng)用舉例例如:求下圖中頂點(diǎn)3至頂點(diǎn)5的一條最短路徑。鏈隊(duì)列的狀態(tài)如下所示:

312475

Q.front

Q.rear3214756897.3圖的遍歷遍歷應(yīng)用舉例1)將鏈隊(duì)列的結(jié)點(diǎn)改為“雙鏈”結(jié)點(diǎn)。即結(jié)點(diǎn)中包含next和priou兩個(gè)指針；2)修改入隊(duì)列的操作。插入新的隊(duì)尾結(jié)點(diǎn)時(shí)，令其priou域的指針指向剛剛出隊(duì)列的結(jié)點(diǎn)，即當(dāng)前的隊(duì)頭指針?biāo)附Y(jié)點(diǎn)；3)修改出隊(duì)列的操作。出隊(duì)列時(shí)，僅移動(dòng)隊(duì)頭指針，而不將隊(duì)頭結(jié)點(diǎn)從鏈表中刪除。修改鏈隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)及其入隊(duì)列和出隊(duì)列的算法7.3圖的遍歷遍歷應(yīng)用舉例typedef

DuLinkListQueuePtr;

voidInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

Q.front->next=Q.rear->next=NULL}voidEnQueue(LinkQueue&Q,QelemTypee){p=(QueuePtr)malloc(sizeof(QNode));p->data=e;p->next=NULL;

p->priou=Q.front

Q.rear->next=p;Q.rear=p;}voidDeQueue(LinkQueue&Q,QelemType&e){

Q.front=Q.front->next;e=Q.front->data}7.4圖的連通性問(wèn)題連通圖的生成樹(shù)：是連通圖的一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有n-1條邊。非連通圖的生成森林：由若干棵生成樹(shù)組成，含圖中全部頂點(diǎn)，但構(gòu)成這些樹(shù)的邊是最少的。思考1：對(duì)連通圖進(jìn)行遍歷，得到的是什么？

——得到的將是一個(gè)極小連通子圖，即圖的生成樹(shù)！由深度優(yōu)先搜索得到的生成樹(shù)，稱(chēng)為深度優(yōu)先搜索生成樹(shù)。由廣度優(yōu)先搜索得到的生成樹(shù)，稱(chēng)為廣度優(yōu)先搜索生成樹(shù)。思考2：對(duì)非連通圖進(jìn)行遍歷，得到的是什么？

——得到的將是各連通分量的生成樹(shù)，即圖的生成森林！例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林圖的生成樹(shù)和生成森林7.4圖的連通性問(wèn)題圖的生成樹(shù)和生成森林V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8說(shuō)明：連通圖的生成樹(shù)不唯一7.4圖的連通性問(wèn)題圖的生成樹(shù)和生成森林所有生成樹(shù)具有以下共同特點(diǎn)：生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同（是連通圖的極小連通子圖）一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)只有n-1條邊在生成樹(shù)中再加一條邊必然形成回路生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹(shù)說(shuō)明7.4圖的連通性問(wèn)題圖的生成樹(shù)和生成森林如何判斷一個(gè)圖就是一棵樹(shù)？遍歷該圖，若遍歷序列正好飽含圖中全部頂點(diǎn)和n-1邊，既是。實(shí)現(xiàn)：可以在遍歷過(guò)程中增加兩個(gè)計(jì)數(shù)器（頂點(diǎn)計(jì)數(shù)器和邊計(jì)數(shù)器，在訪(fǎng)問(wèn)時(shí)計(jì)數(shù)）如何判斷一個(gè)圖有生成樹(shù)？一個(gè)圖有生成樹(shù)，在遍歷時(shí)，必經(jīng)過(guò)n-1邊。思想同上7.4圖的連通性問(wèn)題圖的生成樹(shù)和生成森林

從不同頂點(diǎn)出發(fā)或搜索次序不同，可得到不同的生成樹(shù)

生成樹(shù)的權(quán)：對(duì)連通網(wǎng)絡(luò)來(lái)說(shuō)，邊附上權(quán)，生成樹(shù)也帶權(quán)，我們把生成樹(shù)各邊的權(quán)值總和稱(chēng)為生成樹(shù)的權(quán)

最小代價(jià)生成樹(shù)：在一個(gè)連通網(wǎng)的所有生成樹(shù)中，各邊的代價(jià)之和最小的那棵生成樹(shù)稱(chēng)為該連通網(wǎng)的最小代價(jià)生成樹(shù)（MinimumCostSpanningTree），簡(jiǎn)稱(chēng)為最小生成樹(shù)(MST)。說(shuō)明（續(xù)）7.4圖的連通性問(wèn)題（連通網(wǎng)）的最小生成樹(shù)

假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通

n

個(gè)城市只需要修建n-1條線(xiàn)路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？問(wèn)題：n個(gè)城市間，若任意兩個(gè)城市都有一條通訊線(xiàn)，則最多可設(shè)置n(n-1)/2條線(xiàn)路，但實(shí)際上僅需n-1條線(xiàn)路，即可實(shí)現(xiàn)n個(gè)城市連通通訊。7.4圖的連通性問(wèn)題（連通網(wǎng)）的最小生成樹(shù)問(wèn)題演化要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)——表示城市邊的權(quán)——城市間建立通信線(xiàn)路所需花費(fèi)代價(jià)問(wèn)題分析n個(gè)城市間，最多可設(shè)置n(n-1)/2條線(xiàn)路n個(gè)城市間建立通信網(wǎng)，只需n-1條線(xiàn)路如何在可能的線(xiàn)路中選擇n-1條，

能把所有城市（頂點(diǎn)）均連起來(lái)，

且總耗費(fèi)（各邊權(quán)值之和）最小。16543271317918127524107.4圖的連通性問(wèn)題（連通網(wǎng)）的最小生成樹(shù)

在n個(gè)頂點(diǎn)的連通網(wǎng)中，構(gòu)造網(wǎng)的一棵最小生成樹(shù),即：在e條帶權(quán)的邊中選取

n-1

條邊(不構(gòu)成回路),

使“權(quán)值之和”為最小。該問(wèn)題等價(jià)于：找最經(jīng)濟(jì)通訊網(wǎng)求最小生成樹(shù)如何求最小生成樹(shù)？?jī)煞N方法：Prim算法

Kruskal算法最小生成樹(shù)有如下重要性質(zhì)（MST性質(zhì)）：設(shè)N=(V,{E})是一連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若（u,v）是一條具有最小權(quán)值的邊，其中u∈U，v∈V-U，則存在一棵包含邊（u,v）的最小生成樹(shù)。

換而言之：連通網(wǎng)的最小生成樹(shù)的n-1邊中一定包含連通網(wǎng)中權(quán)值最小的邊。（例如在1-10中選擇3個(gè)數(shù)，使得這三個(gè)數(shù)之和最小，則這三個(gè)數(shù)中必定包含1。）7.4圖的連通性問(wèn)題（連通網(wǎng)）的最小生成樹(shù)7.4圖的連通性問(wèn)題（連通網(wǎng)）的最小生成樹(shù)

假設(shè)不存在這樣一棵包含邊（u,v）的最小生成樹(shù)。任取一棵最小生成樹(shù)T，將（u,v）加入T中。根據(jù)樹(shù)的性質(zhì)，此時(shí)T中必形成一個(gè)包含（u,v）的回路，且回路中必有一條邊(u’,v’)的權(quán)值大于或等于(u,v)的權(quán)值。刪除（u’,v’)，則得到一棵代價(jià)小于等于T的生成樹(shù)T′，且T′為一棵包含邊（u,v）的最小生成樹(shù)。這與假設(shè)矛盾，故該性質(zhì)得證。UuV-Uv我們用反證法來(lái)證明這個(gè)MST性質(zhì)：7.4圖的連通性問(wèn)題（連通網(wǎng)）的最小生成樹(shù)（1）初始狀態(tài)：U={u0},（u0∈V），TE=φ,（2）在uU,vV-U所有的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)，并將邊(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)。（3）重復(fù)（2），直到U=V為止。

此時(shí)TE中必有n-1條邊，T＝(V,{TE}）就是最小生成樹(shù)。設(shè)：N=（V,E）是個(gè)連通網(wǎng)，另設(shè)U為最小生成樹(shù)的頂點(diǎn)集，TE為最小生成樹(shù)的邊集。構(gòu)造步驟:普利姆（Prim）算法7.4圖的連通性問(wèn)題（連通網(wǎng)）的最小生成樹(shù)例1654326513566425131163141643142116432142516543214253[注]：在最小生成樹(shù)的生成過(guò)程中，所選的邊都是一端在U中，另一端在V-U中。選最小邊的過(guò)程是一個(gè)向集合U中添加頂點(diǎn)的過(guò)程。U={1}U={1,3}U={1,3,6}U={1,3,6,4,2,5}U={1,3,6,4,2}U={1,3,6,4}7.4圖的連通性問(wèn)題（連通網(wǎng)）的最小生成樹(shù)

在生成樹(shù)的構(gòu)造過(guò)程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹(shù)上的頂點(diǎn)集

U

和尚未落在生成樹(shù)上的頂點(diǎn)集V-U

，則應(yīng)在所有連通U中頂點(diǎn)u和V-U中頂點(diǎn)v的邊中選取權(quán)值最小的邊（u’，v’），并把v’添加到U中。

一般情況下所添加的頂點(diǎn)應(yīng)滿(mǎn)足下列條件:UV-Uu’v’7.4圖的連通性問(wèn)題（連通網(wǎng)）的最小生成樹(shù)設(shè)計(jì)思路：①增設(shè)一輔助數(shù)組Closedge[n]，以記錄從U到V-U具有最小代價(jià)的邊，每個(gè)數(shù)組分量都有兩個(gè)域：要求：使Colsedge[i].lowcost=min((u,vi))uU計(jì)算機(jī)內(nèi)怎樣實(shí)現(xiàn)Prim（普里姆）算法？

Prime算法特點(diǎn):將頂點(diǎn)歸并，與邊數(shù)無(wú)關(guān)，適于稠密網(wǎng)。故采用鄰接矩陣作為圖的存儲(chǔ)表示。adjvexlowcostvi

在U中的鄰接點(diǎn)u（u，vi）Colsedge[i]V-U中頂點(diǎn)viu與vi之間對(duì)應(yīng)的邊權(quán)u從U（u1~un）中挑選，選擇U中到頂點(diǎn)vi邊的權(quán)值最小的頂點(diǎn)struct{VertexTypeadjvex;//u在U集中的頂點(diǎn)序號(hào)

VRTypelowcost;//邊的權(quán)值}

closedge[MAX_VERTEX_NUM];7.4圖的連通性問(wèn)題（連通網(wǎng)）的最小生成樹(shù)adjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostV-UU65432vclosedge1423561655536426具體示例：有關(guān)程序參