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

數(shù)據(jù)結(jié)構(gòu)第7章圖主要內(nèi)容7.1圖的定義和術語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及其應用7.6最短路徑7.1圖的定義和術語圖(Graph)——圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點的非空有限集

E(G)是邊的有限集合，邊是頂點的無序?qū)蛴行驅(qū)ΑＳ邢驁D——有向圖G是由兩個集合V(G)和E(G)組成的

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

E(G)是有向邊（也稱?。┑挠邢藜希∈琼旤c的有序?qū)?，記?lt;v,w>，v,w是頂點，v為弧尾，w為弧頭無向圖——無向圖G是由兩個集合V(G)和E(G)組成的

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

E(G)是邊的有限集合，邊是頂點的無序?qū)Γ洖椋╲,w）或（w,v)，并且（v,w)=(w,v)

(u,v)<u,v>V=VertexE=Edge7.1圖的定義和術語例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無向圖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圖的定義和術語有向完全圖——有n(n-1)條弧的n個頂點的有向圖無向完全圖——有n(n-1)/2條邊的n個頂點的無向圖稀疏圖--若邊或弧的個數(shù)e<nlogn，則稱作稀疏圖，否則成稠密圖。權(quán)—把圖的邊或弧賦予一個有意義的數(shù)，此數(shù)叫權(quán)帶權(quán)圖-網(wǎng)—弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。子圖——如果圖G(V,E)和圖G‘(V’,E‘),滿足：

V’V

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

圖的練習：判斷下列4種圖形各屬什么類型？7.1圖的定義和術語簡單路徑：路徑上各頂點v1,v2,...,vm

均不互相重復?；芈罚喝袈窂缴系谝粋€頂點v1

與最后一個頂點vm

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

vi出發(fā),沿一些邊經(jīng)過一些頂點

vp1,

vp2,…,

vpm，到達頂點vj。則稱頂點序列

(vivp1vp2...vpmvj)

為從頂點vi到頂點

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

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

）路徑長度：2(5)簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，17.1圖的定義和術語連通圖例3231強連通圖456例2例1245136

在無向圖中,若從頂點vi到頂點vj有路徑,則稱頂點vi與vj是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。

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

在有向圖中,

若對于每一對頂點vi和vj,

都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。

非強連通圖的極大強連通子圖叫做強連通分量。77.1圖的定義和術語

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

//若G中存在頂點u，則返回該頂點在

//圖中“位置”;否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對v賦值value。7.1圖的定義和術語圖的基本操作對鄰接點的操作FirstAdjVex(G,v);

//返回v的“第一個鄰接點”。若該頂點//在G中沒有鄰接點，則返回“空”。NextAdjVex(G,v,w);

//返回v的（相對于w的）“下一個鄰接//點”。若w是v的最后一個鄰接點，則//返回“空”。7.1圖的定義和術語圖的基本操作插入或刪除頂點InsertVex(&G,v);

//在圖G中增添新頂點v。DeleteVex(&G,v);//刪除G中頂點v及其相關的弧。7.1圖的定義和術語圖的基本操作插入和刪除弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是無向的，

//則還增添對稱弧(w,v)。DeleteArc(&G,v,w);

//在G中刪除弧<v,w>，若G是無向的，

//則還刪除對稱弧(w,v)。7.1圖的定義和術語圖的基本操作遍歷DFSTraverse(G,v,Visit());//從頂點v起深度優(yōu)先遍歷圖G，并對每//個頂點調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());

//從頂點v起廣度優(yōu)先遍歷圖G，并對每//個頂點調(diào)用函數(shù)Visit一次且僅一次。7.2圖的存儲結(jié)構(gòu)一、圖的數(shù)組(鄰接矩陣)存儲表示二、圖的鄰接表存儲表示三、有向圖的十字鏈表存儲表示四、無向圖的鄰接多重表存儲表示7.2圖的存儲結(jié)構(gòu)圖的數(shù)組存儲表示用兩個數(shù)組分別存儲頂點信息和頂點之間的關系信息(鄰接矩陣—表示頂點間相鄰關系的矩陣)定義：設G=(V,E)是有n1個頂點的圖，G的鄰接矩陣A（二維數(shù)組）是具有以下性質(zhì)的n階方陣：例G12413例15324G27.2圖的存儲結(jié)構(gòu)圖的數(shù)組存儲表示

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

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

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

n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。對稀疏圖而言尤其浪費空間。鄰接矩陣法優(yōu)點：鄰接矩陣法缺點：typedefstructArcCell{//弧的定義

VRTypeadj;//VRType是頂點關系類型,

//對無權(quán)圖，用1或0表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。

InfoType*info;//該弧相關信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];#defineINFINITY INT_MAX//定義無窮大∞#defineMAX_VERTEX_NUM 20

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

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

AdjMatrixarcs;//鄰接矩陣，可設二維

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

GraphKindkind;//圖的種類標志

}MGraph;7.2圖的存儲結(jié)構(gòu)圖的數(shù)組（鄰接矩陣）存儲表示實現(xiàn)7.2圖的存儲結(jié)構(gòu)圖的數(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圖的存儲結(jié)構(gòu)圖的鄰接表存儲表示表頭結(jié)點結(jié)構(gòu):數(shù)據(jù)域（data）用于存儲頂點的名或其它有關信息；

鏈域（firstarc）用于指向鏈表中第一個頂點（即與頂點

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

info存儲和邊相關的信息(若無，則置空NULL)

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

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

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

structnode*nextarc;

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

//VRTypeweight;

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

}ArcNode;

//定義指向該弧相關信息的指針

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

structArcNode*firstarc;//指示第一個鄰接點}VNode，AdjList[MAX_VERTEX_NUM];vexdatafirstarctypedefstruct{

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

AdjList

vertices;//頂點向量

intvexnum,arcnum;GraphKindkind;//圖的種類標志

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

2^^^adjvexnextarc5e435^

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

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

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

例G1bdac1234acdbvexdatafirstarc41^1^^3^adjvex

nextarc1234acdbvexdatafirstarc2341^^^^adjvexnextarc7.2圖的存儲結(jié)構(gòu)圖的鄰接表存儲表示7.2圖的存儲結(jié)構(gòu)圖的鄰接表存儲表示討論：鄰接表與鄰接矩陣有什么異同之處？聯(lián)系：鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于該行中非零元素的個數(shù)。2.區(qū)別：①對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關）。②鄰接矩陣的空間復雜度為O(n2),而鄰接表的空間復雜度為O(n+e)。e隨n的改變而變化--函數(shù)關系3.用途：鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲（e<<n2)7.2圖的存儲結(jié)構(gòu)圖的鄰接表存儲表示

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

D0

A

4

11

B54

02C533D524

E

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

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

1.

57DG2.

ABCDE3.

ABAEBCCDDADBEC

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

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

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

{

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

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

//輸入頂點

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

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

//輸入一條邊（?。┑氖键c和終點

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

if(!pi)exit(-1);

//存儲分配失敗

pi->adjvex=j;

//對弧結(jié)點賦鄰接點"位置“

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

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

else

{w=0;p=NULL;}

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

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

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

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

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

pj=newArcNode;

if(!pi)exit(-1);

//存儲分配失敗

pj->adjvex=i;

//對邊結(jié)點賦鄰接點“位置”

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

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

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

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

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

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

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

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

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

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

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

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

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

ilink

jvex

jlinkinfoconstMAX_VERTEX_NUM=20;

typedefemnu{unvisited,visited}VisitIf;typedefstructEdgeNode{

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

VisitIfmark;

//訪問標記

intivex,jvex;

//該邊依附的兩個頂點（vi，vj）在圖中的位置

structEdgeNode*ilink,*jlink;//分別指向依附這兩個頂點的下一條邊

VRTypeweight;

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

InfoType*info;

//與該邊相關信息的指針

};datafirstedge

頂點結(jié)點：typedefstruct{

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

VertexTypedata;

EdgeNode*firstedge;

//指向第一條依附該頂點的邊

}VexNode;typedefstruct{

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

VexNodeadjmulist[MAX_VERTEX_NUM];

intvexnum,edgenum;

//無向圖的當前頂點數(shù)和邊數(shù)

GraphKindkind;

//圖的種類標志

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

D

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

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

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

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

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

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

：

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

⑵、然后依次搜索vi的每一個鄰接點vj

；⑶、若vj未被訪問過，則以vj為新的初始出發(fā)點，重復⑴若vj已被訪問過，則返回到vi另一個鄰接點，重復⑶

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

Vi的鄰接點Vj

。

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

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

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

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

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

//返回V的(相對于w)下一鄰接點

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

//對v的尚未訪問的鄰接頂點w遞歸調(diào)用DFS}//DFS提示：

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

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

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

Status(*Visit)(intv))

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

VisitFunc=Visit;//初始化訪問函數(shù)

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪問標志數(shù)組初始化

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

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

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

個表結(jié)點，但只需掃描e

個結(jié)點即可完成遍歷（∵判斷訪問標志），加上訪問

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

廣度優(yōu)先搜索遍歷圖時，對連通圖，從起始點V到其余各頂點必定存在路徑，并且訪問頂點的次序是按頂點的路徑長度遞增進行的。

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

的路徑長度為1；

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

的路徑長度為2；V1->v8

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

fr遍歷序列：14325例1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^227.3圖的遍歷廣度優(yōu)先搜索遍歷圖開始訪問V,置標志求U鄰接點WW存在嗎U下一鄰接點WW訪問過結(jié)束NYNY初始化隊列V入隊隊列空嗎隊頭出隊U訪問W,置標志W(wǎng)入隊NaaYBFS開始標志數(shù)組初始化Vi=0Vi訪問過？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;//初始化訪問標志

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

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

if(!visited[v])//v尚未訪問

{

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

G,v)；開始標志數(shù)組初始化Vi=0Vi訪問過BFSVi=Vi+1Vi<Vexnums結(jié)束NNYYvoidBFS(GraphG,

intv){visited[v]=TRUE;Visit(v);//訪問vEnQueue(Q,v);//v入隊列while(!QueueEmpty(Q)){

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

for(w=FirstAdjVex(G,u);

w!=0;

w=NextAdjVex(G,u,w))

if(!visited[w]){

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

EnQueue(Q,w);

//訪問的頂點w入隊列

}//if

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

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

簡單路徑2.

求兩個頂點之間的一條路徑長度最短的路徑7.3圖的遍歷遍歷應用舉例7.3圖的遍歷遍歷應用舉例1.

求一條從頂點i到頂點s的簡單路徑

求從頂點b到頂點k的一條簡單路徑。

從頂點b

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

假設找到的第一個鄰接點是a，則得到的結(jié)點訪問序列為:

b

a

dhc

e

k

fg。

假設找到的第一個鄰接點是c，則得到的結(jié)點訪問序列為:

b

chdae

k

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

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

從頂點i

到頂點s,若存在路徑，則從頂點

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

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

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

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

visited[v]=TRUE;//訪問第v個頂點，能不被重復訪問

Append(PATH,getVertex(v));

//第v個頂點加入路徑

//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);

//從路徑上刪除頂點v

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

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

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

elseif(k>0){visited[v]=TRUE;//訪問第v個頂點

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

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);

//從路徑上刪除頂點v

}//求有向圖G的頂點v到s是否存在長度為k的簡單路徑7.3圖的遍歷遍歷應用舉例2.

求兩個頂點之間的一條路徑長度最短的路徑課下思考

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

312475

Q.front

Q.rear3214756897.3圖的遍歷遍歷應用舉例1)將鏈隊列的結(jié)點改為“雙鏈”結(jié)點。即結(jié)點中包含next和priou兩個指針；2)修改入隊列的操作。插入新的隊尾結(jié)點時，令其priou域的指針指向剛剛出隊列的結(jié)點，即當前的隊頭指針所指結(jié)點；3)修改出隊列的操作。出隊列時，僅移動隊頭指針，而不將隊頭結(jié)點從鏈表中刪除。修改鏈隊列的結(jié)點結(jié)構(gòu)及其入隊列和出隊列的算法7.3圖的遍歷遍歷應用舉例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圖的連通性問題連通圖的生成樹：是連通圖的一個極小連通子圖，它含有圖中全部頂點，但只有n-1條邊。非連通圖的生成森林：由若干棵生成樹組成，含圖中全部頂點，但構(gòu)成這些樹的邊是最少的。思考1：對連通圖進行遍歷，得到的是什么？

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

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

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

生成樹的權(quán)：對連通網(wǎng)絡來說，邊附上權(quán)，生成樹也帶權(quán)，我們把生成樹各邊的權(quán)值總和稱為生成樹的權(quán)

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

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

n

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

能把所有城市（頂點）均連起來，

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

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

n-1

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

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

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

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

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

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

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

U

和尚未落在生成樹上的頂點集V-U

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

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

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

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

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

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