數(shù)據(jù)結(jié)構(gòu)簡明教程（第3版）課件 第7章圖(上)

第7章圖7.1圖的基本概念7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4生成樹和最小生成樹7.5最短路徑7.6拓?fù)渑判?.7AOE網(wǎng)與關(guān)鍵路徑第7章圖1/887.1圖的基本概念7.1.1圖的定義無論多么復(fù)雜的圖都是由頂點和邊構(gòu)成的。采用形式化的定義，圖G（Graph）由兩個集合V（Vertex）和E（Edge）組成，記為G=(V,E)，其中V是頂點的有限集合，記為V(G)，E是連接V中兩個不同頂點（頂點對）的邊的有限集合，記為E(G)。7.1圖的基本概念2/88對于含有n個頂點的圖，通常用字母或自然數(shù)來唯一標(biāo)識圖中頂點（頂點的編號）。本書約定用數(shù)字i（0≤i≤n-1）表示第i個頂點的編號。7.1圖的基本概念3/88

【例7.1】一個圖G1=(V1，E1)，其中：

V1={0，1，2，3，4}E1={(0,1)，(1,2)，(2,3)，(3,4)，(2,4)，(0,3)}另一個圖G2=(V2，E2)，其中：

V2={0，1，2，3，4}

E2={<0,1>，<1,2>，<1,3>，<2,4>，<0,4>，<4,3>，<3,2>}畫出這兩個圖的邏輯結(jié)構(gòu)。7.1圖的基本概念4/88

它們的邏輯結(jié)構(gòu)如圖7.1所示，從中看到圖G1是無向圖，圖G2是有向圖。V1={0，1，2，3，4}E1={(0,1)，(1,2)，(2,3)，(3,4)，(2,4)，(0,3)}0124301243V2={0，1，2，3，4}E2={<0,1>，<1,2>，<1,3>，<2,4>，<0,4>，<4,3>，<3,2>}7.1圖的基本概念5/887.1.2圖的基本術(shù)語（1）無向圖和有向圖

對于一個圖G，若邊集E(G)為無向邊的集合，則稱該圖為無向圖。例如，圖7.1(a)中的圖就是一個無向圖。對于一個圖G，若邊集E(G)為有向邊的集合，則稱該圖為有向圖。例如，圖7.1(b)中的圖就是一個有向圖。01243012437.1圖的基本概念6/88（2）端點和相鄰點在一個無向圖中，若存在一條邊(i,j)，則稱頂點i、j為該邊的兩個端點，并稱它們互為相鄰點（或者鄰接點）。

例如，圖7.1(a)中，頂點0和頂點1是兩個端點，它們互為相鄰點。01243注意：端點和相鄰點是相對一條邊的7.1圖的基本概念7/88在一個有向圖中，若存在一條邊<i,j>，則稱此邊是頂點i的一條出邊，同時也是頂點j的一條入邊，稱頂點i和j分別為此邊的起始端點（簡稱為起點）和終止端點（簡稱終點）。

例如，圖7.1(b)中，對于邊<0,1>，該邊是頂點0的出邊，頂點1的入邊，同時，頂點0稱為起點，頂點1稱為終點。012437.1圖的基本概念8/88（3）度、入度和出度頂點v的度記為D(v)。對于無向圖，每個頂點的度定義為以該頂點為一個端點的邊數(shù)。

對于有向圖，頂點v的度分為入度和出度，入度是以該頂點為終點的入邊數(shù)目；出度是以該頂點為起點的出邊數(shù)目，該頂點的度等于其入度和出度之和。

例如，圖7.1(a)中，D(0)=2。012437.1圖的基本概念9/88在圖7.1(b)中，頂點4的入度為2，出度為1，所以D(4)=3。012437.1圖的基本概念10/88若一個圖（無論有向圖或無向圖）中有n個頂點和e條邊，每個頂點的度為di（0≤i≤n-1），則有：也就是說，一個圖中所有頂點的度之和等于邊數(shù)的兩倍。因為圖中每條邊分別作為兩個相鄰點的度各計一次。e＝7.1圖的基本概念11/88

【例7.2】一個無向圖中有16條邊，度為4的頂點有3個，度為3的頂點有4個，其余頂點的度均小于3，則該圖至少有（）個頂點。

A.10

B.11 C.12 D.13設(shè)該圖有n個頂點，圖中度為i的頂點數(shù)為ni（0≤i≤4），n4=3，n3=4。要使頂點數(shù)最少，該圖應(yīng)是連通的，即n0=0，n=n4+n3+n2+n1+n0=7+n2+n1，即n2+n1=n-7。度之和=4×3+3×4+2×n2+n1=24+2n2+n1≤24+2(n2+n1)=24+2×(n-7)=10+2n。而度之和=2e=32，所以有10+2n≥32，即n≥11。7.1圖的基本概念12/88（4）子圖設(shè)有兩個圖G=(V,E)和G'=(V',E')，若V'是V的子集，即V'

V，且E'是E的子集，即E'

E，則稱G'是G的子圖。7.1圖的基本概念13/88

注意：對于一個圖G=(V,E)，V'是V的子集，即V'

V，E'是E的子集，即E'

E。而(V',E')可能不是一個圖，所以由V的子集和E的子集并非一定構(gòu)成G的子圖。01243而V'={0,2}，E'={(0,3)，(2,3)}并不是其子圖，因為(V',E')本身不是一個圖。027.1圖的基本概念14/88（5）完全無向圖和完全有向圖

對于無向圖，若具有n(n-1)/2條邊，則稱之為完全無向圖。例如，圖7.2(a)是完全無向圖G3，這里n=4，邊數(shù)為6。12307.1圖的基本概念15/88對于有向圖，若具有n(n-1)條邊，則稱之為完全有向圖。

例如，圖7.2(b)是完全有向圖G4，這里n=4，邊數(shù)為12。12307.1圖的基本概念16/88（6）稀疏圖和稠密圖邊數(shù)較少（邊數(shù)e<<nlog2n，其中n為頂點數(shù)）的圖稱為稀疏圖。邊總較多的圖稱為稠密圖。7.1圖的基本概念17/88（7）路徑和路徑長度在一個圖G中，從頂點i到頂點j的一條路徑是一個頂點序列i=i0、i1、…、im=j，若是無向圖，則(ik-1,ik)∈E(G)，（1≤k≤m），若該圖是有向圖，則<ik-1,ik>∈E(G)，（1≤k≤m），其中頂點i稱為該路徑的開始點，頂點j稱為該路徑的結(jié)束點。路徑長度是指一條路徑上經(jīng)過的邊的數(shù)目。7.1圖的基本概念18/88（8）簡單路徑若一條路徑的頂點序列中頂點不重復(fù)出現(xiàn)，稱該路徑為簡單路徑。

例如，圖7.1(a)中，路徑0→1→2→4是一條簡單路徑，其長度為3。012437.1圖的基本概念19/88圖7.1(b)中，路徑0→1→3→2是一條簡單路徑，其長度也為3。012437.1圖的基本概念20/88（9）回路（環(huán)）若一條路徑上的開始點和結(jié)束點為同一個頂點，則稱該路徑為回路（環(huán)）。除開始點與結(jié)束點相同外，其余頂點不重復(fù)出現(xiàn)的回路稱為簡單回路（簡單環(huán)）。

例如，圖7.1(a)中，路徑0→1→2→4→3→0是一條回路（環(huán)），也是一條簡單回路（簡單環(huán)）。012437.1圖的基本概念21/88（10）連通、連通圖和連通分量在無向圖G中，若從頂點i到頂點j有路徑，則稱頂點i和j是連通的。若圖G中任意兩個頂點都是連通的，則稱G為連通圖，否則為非連通圖。無向圖G中極大連通子圖稱為G的連通分量。

例如，圖7.1(a)的連通分量就是自身，因為該圖是連通圖。012437.1圖的基本概念22/88（11）強連通圖和強連通分量在有向圖G中，若任意兩個頂點i和j都是連通的，即從頂點i到j(luò)和從頂點j到i都存在路徑，則稱該圖是強連通圖。有向圖G中極大強連通子圖稱為G的強連通分量。

7.1圖的基本概念23/88對于圖7.1(b)的有向圖，頂點0的入度為0，也就是說其余頂點都沒有到達頂點0的路徑，所以單個頂點0是一個強連通分量；頂點1只有一條從頂點0到它的入邊，除頂點0外其余頂點沒有到達頂點1的路徑，所以單個頂點1也是一個強連通分量；點2、3、4構(gòu)成一個有向環(huán)，這些頂點之間都有路徑，該圖的強連通分量。0124301243強連通分量7.1圖的基本概念24/88（12）權(quán)和網(wǎng)在一個圖中，每條邊可以標(biāo)上具有某種含義的數(shù)值，該數(shù)值稱為該邊的權(quán)。邊上帶權(quán)的圖稱為帶權(quán)圖，也稱為網(wǎng)。

圖7.4中的圖G5就是一個帶權(quán)圖。本書中規(guī)定所有邊的權(quán)均為非負(fù)數(shù)。0132414623757.1圖的基本概念25/88

【例7.3】如果圖G是一個具有n個頂點的連通圖，那么G最多有多少條邊？G最少有多少條邊？

如果圖G'是一個具有n個頂點的強連通圖，那么G'最多有多少條邊？G'最少有多少條邊？圖G為完全無向圖時邊最多，即圖G最多有n(n-1)/2條邊；圖G為一棵樹時邊最少，即G最少有n-1條邊。0123n=47.1圖的基本概念圖G為連通圖：26/88圖G為完全有向圖時邊最多，即圖G最多有n(n-1)條邊；圖G為一棵樹時邊最少，即G最少有n條邊。0123n=47.1圖的基本概念圖G為強連通圖:27/887.1.3圖的基本操作圖的基本運算如下：建立圖CreateGraph(G)：建立圖G的某種存儲結(jié)構(gòu)。銷毀圖DestroyGraph(G)：釋放圖G占用的內(nèi)存空間。輸出圖DispGraph(G)：顯示圖G的結(jié)構(gòu)。求頂點的度Degree(G,v)：求圖G中頂點v的度。7.1圖的基本概念28/887.2圖的存儲結(jié)構(gòu)7.2.1鄰接矩陣鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n個頂點的圖，頂點編號依次為0、1、…、n-1，則G的鄰接矩陣是具有如下定義的n階方陣A。7.2圖的存儲結(jié)構(gòu)A[i][j]=對于無向圖，(i,j)或(j,i)∈E(G)；對于有向圖，<i,j>∈E(G)i=j其他情況100若G是不帶權(quán)的圖：29/88A[i][j]=對于無向圖，(i,j)或(j,i)∈E(G)；對于有向圖，<i,j>∈E(G)i=j其他情況wij0∞若G是帶權(quán)圖或網(wǎng)，則鄰接矩陣可定義為（其中wij為邊(i,j)或<i,j>的權(quán)）：7.2圖的存儲結(jié)構(gòu)30/8801243A1=01234001010110100201011310101400110無向圖時一定為對稱矩陣頂點1的度為27.2圖的存儲結(jié)構(gòu)31/88A2=01234001001100110200001300100400010有向圖時不一定為對稱矩陣頂點1的出度為201243頂點1的入度為17.2圖的存儲結(jié)構(gòu)32/88A3=0123400126∞1∞0∞452∞∞0∞33∞∞∞0∞4∞∞∞70有向圖時不一定為對稱矩陣頂點1的出度為2頂點1的入度為10132414623757.2圖的存儲結(jié)構(gòu)33/88圖鄰接矩陣的特點：對于n個頂點e條邊的圖采用鄰接矩陣存儲時占用存儲空間為O(n2)，與邊數(shù)e無關(guān)（不考慮壓縮存儲），特別適合存儲稠密圖；任何圖的鄰接矩陣表示是唯一的；圖采用鄰接矩陣存儲時判斷兩個頂點i、j之間是否有邊十分容易。7.2圖的存儲結(jié)構(gòu)34/88圖的鄰接矩陣類型聲明：#defineMAXVEX100

//圖中最大頂點個數(shù)typedefcharVertexType[10];

//定義VertexType為字符串類型typedefstructvertex{intadjvex;

//頂點編號

VertexTypedata;

//頂點的信息}VType;

//頂點類型typedefstructgraph{intn,e;

//n為實際頂點數(shù),e為實際邊數(shù)

VType

vexs[MAXVEX];

//頂點集合

intedges[MAXVEX][MAXVEX];

//邊的集合}

MatGraph;

//圖的鄰接矩陣類型7.2圖的存儲結(jié)構(gòu)35/88在鄰接矩陣上實現(xiàn)圖的主要基本運算的算法如下。（1）建立圖的鄰接矩陣運算算法由鄰接矩陣數(shù)組A、頂點數(shù)n和邊數(shù)e建立圖G的鄰接矩陣存儲結(jié)構(gòu)。voidCreateGraph(MatGraph&g,intA[][MAXVEX],intn,inte){inti,j;

g.n=n;g.e=e;

for(i=0;i<n;i++)for(j=0;j<n;j++)

g.edges[i][j]=A[i][j];}7.2圖的存儲結(jié)構(gòu)36/88（2）銷毀圖運算算法這里鄰接矩陣是圖的一種順序存儲結(jié)構(gòu)，其內(nèi)存空間是由系統(tǒng)自動分配的，在不再需要時由系統(tǒng)自動釋放其空間。所以對應(yīng)的函數(shù)不含任何語句。voidDestroyGraph(MatGraphg){}7.2圖的存儲結(jié)構(gòu)37/88（3）輸出圖運算算法將圖G的鄰接矩陣存儲結(jié)構(gòu)輸出到屏幕上。voidDispGraph(MatGraphg){inti,j;

for(i=0;i<g.n;i++)

{for(j=0;j<g.n;j++)

{if(g.edges[i][j]<INF)

printf("%4d",g.edges[i][j]);

else

printf("%4s","∞");}printf("\n");}}7.2圖的存儲結(jié)構(gòu)38/88（4）求頂點度運算算法對于無向圖和有向圖，求頂點度有所不同。依據(jù)定義，求無向圖G中頂點v的度的算法如下：intDegree1(MatGraphg,intv)

//求無向圖中頂點的度{inti,d=0;

if(v<0||v>=g.n)return-1;

//頂點編號錯誤返回-1

for(i=0;i<g.n;i++){if(g.edges[v][i]>0&&g.edges[v][i]<INF)

d++;

//統(tǒng)計第v行既不為0也不為∞的邊數(shù)即度

}returnd;}7.2圖的存儲結(jié)構(gòu)39/88求有向圖G中頂點v的度的算法如下：intDegree2(MatGraphg,intv)

//求有向圖中頂點的度{inti,d1=0,d2=0,d;

if(v<0||v>=g.n)return-1; //頂點編號錯誤返回-1for(i=0;i<g.n;i++){if(g.edges[v][i]>0&&g.edges[v][i]<INF)

d1++;

//統(tǒng)計第v行既不為0也不為∞的邊數(shù)即出度

}for(i=0;i<g.n;i++){if(g.edges[i][v]>0&&g.edges[i][v]<INF)

d2++;

//統(tǒng)計第v列既不為0也不為∞的邊數(shù)即入度

}d=d1+d2;

returnd;}7.2圖的存儲結(jié)構(gòu)40/887.2.2鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鄰接表中，對圖中每個頂點建立一個帶頭結(jié)點的單鏈表，把該頂點的所有相鄰點串起來。所有的頭結(jié)點構(gòu)成一個數(shù)組，稱為頭結(jié)點數(shù)組，用adjlist表示，第i個單鏈表adjlist[i]中的結(jié)點表示依附于頂點i的邊，也就是說頭結(jié)點數(shù)組元素的下標(biāo)與頂點編號一致。

7.2圖的存儲結(jié)構(gòu)41/88每個單鏈表中每個結(jié)點由3個域組成：為了統(tǒng)一，對于不帶權(quán)圖，weight域均置為1；對于帶權(quán)圖，weight置為相應(yīng)邊的權(quán)值。頂點域adjvex（用以指示該相鄰點在頭結(jié)點數(shù)組中的下標(biāo)）權(quán)值域weight（存放對應(yīng)邊的權(quán)值）指針域nextarc（用以指向依附于頂點i的下一條邊所對應(yīng)的結(jié)點）7.2圖的存儲結(jié)構(gòu)adjvexweightnextarc**42/8801243v01131∧v10121∧v2113141∧v3012141∧v42131∧datafirstarcadjvexweightnextarc頭結(jié)點邊結(jié)點01234頭結(jié)點數(shù)組adjlist頂點1的度為27.2圖的存儲結(jié)構(gòu)43/8801243v01141∧v12131∧v241∧v321∧v431∧012347.2圖的存儲結(jié)構(gòu)44/88013241462375v01136∧022v134145∧v243∧2v3∧3v437∧47.2圖的存儲結(jié)構(gòu)45/88圖鄰接表的特點：對于n個頂點e條邊的圖采用鄰接表存儲時占用存儲空間為O(n+e)，與邊數(shù)e有關(guān)，特別適合存儲稀疏圖；圖的鄰接表表示不一定是唯一的，這是因為鄰接表的每個單鏈表中，各結(jié)點的順序是任意的；圖采用鄰接表存儲時查找一個頂點的所有相鄰頂點十分容易。7.2圖的存儲結(jié)構(gòu)46/88一個圖的鄰接表存儲結(jié)構(gòu)的類型聲明如下：typedefcharVertexType[10]; //VertexType為字符串類型typedefstructedgenode{intadjvex;

//相鄰點序號

intweight;

//邊的權(quán)值

structedgenode*nextarc;

//下一條邊的頂點}ArcNode; //每個頂點建立的單鏈表中邊結(jié)點的類型typedefstructvexnode{VertexTypedata;

//存放一個頂點的信息

ArcNode*firstarc;

//指向第一條邊結(jié)點}VHeadNode; //單鏈表的頭結(jié)點類型typedefstruct{intn,e;

//n為實際頂點數(shù),e為實際邊數(shù)

VHeadNode

adjlist[MAXVEX];

//單鏈表頭結(jié)點數(shù)組}AdjGraph;

//圖的鄰接表類型7.2圖的存儲結(jié)構(gòu)47/88圖編程要領(lǐng)：牢牢掌握數(shù)據(jù)的存儲結(jié)構(gòu)?；舅惴ㄔO(shè)計思路。并用C/C++語句實現(xiàn)。7.2圖的存儲結(jié)構(gòu)48/88在鄰接表上實現(xiàn)圖的主要基本運算的算法如下。（1）建立圖的鄰接表運算算法由鄰接矩陣數(shù)組A、頂點數(shù)n和邊數(shù)e建立圖G的鄰接表存儲結(jié)構(gòu)。先創(chuàng)建鄰接表頭結(jié)點數(shù)組，并置所有頭結(jié)點的firstarc為NULL。遍歷鄰接矩陣數(shù)組A，當(dāng)A[i][j]≠0且A[i][j]≠∞時，說明有一條從頂點i到頂點j的邊，建立一個邊結(jié)點p，置其adjvex域為j，其weight域為A[i][j]（aij），將p結(jié)點插入到頂點i的單鏈表頭部。7.2圖的存儲結(jié)構(gòu)基本思路49/88頭結(jié)點邊結(jié)點注意：圖中每個頂點有一個頭結(jié)點，每條邊有一個邊結(jié)點（無向圖一條邊對應(yīng)2個邊結(jié)點）。vi****∧ijaijp…頂點i到j(luò)有邊：實現(xiàn)語句：p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;引用方式：G->adjlist[i].firstarc7.2圖的存儲結(jié)構(gòu)50/88voidCreateGraph(AdjGraph*&G,intA[][MAXVEX],intn,inte){inti,j;

ArcNode*p;

G=(AdjGraph*)malloc(sizeof(AdjGraph));

G->n=n;G->e=e;

for(i=0;i<G->n;i++) //鄰接表中所有頭結(jié)點的指針域置空G->adjlist[i].firstarc=NULL;

for(i=0;i<G->n;i++) //檢查A中每個元素{for(j=G->n-1;j>=0;j--)

{if(A[i][j]>0&&A[i][j]<INF)

//存在一條邊

{p=(ArcNode*)malloc(sizeof(ArcNode));//創(chuàng)建結(jié)點pp->adjvex=j;

p->weight=A[i][j];

p->nextarc=G->adjlist[i].firstarc;//頭插法插入p

G->adjlist[i].firstarc=p;

}}}}7.2圖的存儲結(jié)構(gòu)51/88（2）銷毀圖運算算法鄰接表的頭結(jié)點和邊結(jié)點都是采用malloc函數(shù)分配的，在不再需要時應(yīng)用free函數(shù)釋放所有分配的空間。7.2圖的存儲結(jié)構(gòu)

基本思路：通過adjlist數(shù)組遍歷每個單鏈表，釋放所有的邊結(jié)點，最后釋放adjlist數(shù)組的空間。52/88voidDestroyGraph(AdjGraph*&G) //銷毀圖{inti;

ArcNode*pre,*p;

for(i=0;i<G->n;i++) //遍歷所有的頭結(jié)點

{pre=G->adjlist[i].firstarc;

if(pre!=NULL)

{p=pre->nextarc;

while(p!=NULL)//釋放adjlist[i]的所有邊結(jié)點

{free(pre);

pre=p;p=p->nextarc;

}

free(pre);

}

}

free(G);

//釋放G所指的頭結(jié)點數(shù)組的內(nèi)存空間}7.2圖的存儲結(jié)構(gòu)53/88（3）輸出圖運算算法輸出圖G的鄰接表存儲結(jié)構(gòu)。voidDispGraph(AdjGraph*G)

//輸出圖的鄰接表{ArcNode*p;

inti;

for(i=0;i<G->n;i++) //遍歷所有的頭結(jié)點{ printf("[%2d]",i); p=G->adjlist[i].firstarc; //p指向第一個相鄰點

if(p!=NULL)

printf("→"); while(p!=NULL)

{printf("%d(%d)",p->adjvex,p->weight);

p=p->nextarc;

//p移向下一個相鄰點

} printf("\n");

}}7.2圖的存儲結(jié)構(gòu)54/88（4）求頂點度運算算法對于無向圖和有向圖，求頂點度有所不同。依據(jù)定義，求無向圖G中頂點v的度的算法如下：intDegree1(AdjGraph*G,intv)//求無向圖G中頂點v的度{intd=0;

ArcNode*p;

if(v<0||v>=G->n)return-1; //頂點編號錯誤返回-1

p=G->adjlist[v].firstarc;

while(p!=NULL) //統(tǒng)計v頂點的單鏈表中邊結(jié)點個數(shù)即度

{d++;

p=p->nextarc;

}

returnd;}7.2圖的存儲結(jié)構(gòu)55/88求有向圖G中頂點v的度的算法如下：intDegree2(AdjGraph*G,intv)//求有向圖G中頂點v的度{inti,d1=0,d2=0,d;ArcNode*p;

if(v<0||v>=G->n)

return-1;

//頂點編號錯誤返回-1

p=G->adjlist[v].firstarc;

while(p!=NULL)

//統(tǒng)計v的單鏈表中邊結(jié)點個數(shù)即出度

{d1++;

p=p->nextarc;

}

for(i=0;i<G->n;i++)//統(tǒng)計邊結(jié)點中adjvex為v的個數(shù)即入度

{p=G->adjlist[i].firstarc;

while(p!=NULL)

{if(p->adjvex==v)d2++;

p=p->nextarc;

}

}

d=d1+d2;

returnd;}7.2圖的存儲結(jié)構(gòu)56/88【例7.7】對于具有n個頂點的有向圖G，設(shè)計以下兩個算法：（1）設(shè)計一個將鄰接矩陣g轉(zhuǎn)換為鄰接表G的算法；（2）設(shè)計一個將鄰接表G轉(zhuǎn)換為鄰接矩陣g的算法。先分配G的內(nèi)存空間并將所有頭結(jié)點的firstarc域置為NULL。遍歷鄰接矩陣g，查找元素值不為0且不為∞的元素g.edges[i][j]，找到這樣的元素后創(chuàng)建一個邊結(jié)點p，將其插入到G->adjlist[i]單鏈表的首部。7.2圖的存儲結(jié)構(gòu)（1）設(shè)計一個將鄰接矩陣g轉(zhuǎn)換為鄰接表G的算法。57/88voidMatToAdj(MatGraphg,AdjGraph*&G)

//將鄰接矩陣g轉(zhuǎn)換成鄰接表G{inti,j;ArcNode*p;

G=(AdjGraph*)malloc(sizeof(AdjGraph));

for(i=0;i<g.n;i++) //鄰接表中所有頭結(jié)點的指針域置初值G->adjlist[i].firstarc=NULL;

for(i=0;i<g.n;i++) //檢查鄰接矩陣中每個元素

{

for(j=g.n-1;j>=0;j--){if(g.edges[i][j]!=0&&g.edges[i][j]!=INF)//有一條邊

{p=(ArcNode*)malloc(sizeof(ArcNode));//創(chuàng)建結(jié)點p

p->adjvex=j;

p->weight=g.edges[i][j];

p->nextarc=G->adjlist[i].firstarc;//頭插法插入pG->adjlist[i].firstarc=p;}

}}

G->n=g.n;G->e=g.e;

//置頂點數(shù)和邊數(shù)}7.2圖的存儲結(jié)構(gòu)58/88先將鄰接矩陣g中所有元素初始化：對角線元素置為0，其他元素置為∞。然后遍歷鄰接表的每個單鏈表，當(dāng)訪問到G->adjlist[i]單鏈表的結(jié)點p時，將鄰接矩陣g的元素g.edges[i][p->adjvex]修改為p->weight。7.2圖的存儲結(jié)構(gòu)（2）設(shè)計一個將鄰接表G轉(zhuǎn)換為鄰接矩陣g的算法59/88voidAdjToMat(AdjGraph*G,MatGraph&g) //將鄰接表G轉(zhuǎn)換成鄰接矩陣g{inti,j;

ArcNode*p;

for(i=0;i<G->n;i++){for(j=0;j<G->n;j++){if(i==j)g.edges[i][i]=0; //對角線置為0

elseg.edges[i][j]=INF;}}for(i=0;i<G->n;i++)

{p=G->adjlist[i].firstarc;

while(p!=NULL)

{g.edges[i][p->adjvex]=p->weight;

p=p->nextarc;

}

}

g.n=G->n;g.e=G->e;

//置頂點數(shù)和邊數(shù)}7.2圖的存儲結(jié)構(gòu)60/887.3圖的遍歷給定一個圖G=(V,E)和其中的任一頂點v，從頂點v出發(fā)，訪問圖G中的所有頂點而且每個頂點僅被訪問一次，這一過程稱為圖的遍歷。為了避免同一頂點被訪問多次，在遍歷圖的過程中，必須記下每個已訪問過的頂點。為此設(shè)一個輔助數(shù)組visited[]，用以標(biāo)記頂點是否被訪問過，初始均為0（false）。一個頂點i被訪問，則visited[i]=1（true）。7.3圖的遍歷61/887.3.1深度優(yōu)先遍歷算法深度優(yōu)先遍歷（DepthFirstSearch，簡稱DFS）：訪問頂點v；選擇一個與頂點v相鄰且沒被訪問過的頂點w，從w出發(fā)深度優(yōu)先遍歷。直到圖中與v相鄰的所有頂點都被訪問過為止。7.3圖的遍歷62/88例如，對于圖7.8(a)的鄰接表，從頂點0出發(fā)的深度優(yōu)先遍歷序列是0、1、2、3、4。v01131∧v10121∧v2113141∧v3012141∧v42131∧頭結(jié)點邊結(jié)點012347.3圖的遍歷63/88實現(xiàn)深度優(yōu)先遍歷的遞歸算法如下：visited[MAXVEX]={0}; //全局變量voidDFS(AdjGraph*G,intv){intw;ArcNode*p;

printf("%d",v); //訪問v頂點

visited[v]=1;

p=G->adjlist[v].firstarc; //找v的第一個相鄰點

while(p!=NULL) //找v的所有相鄰點

{ w=p->adjvex; //頂點v的相鄰點w if(visited[w]==0) //頂點w未訪問過

DFS(G,w);

//從w出發(fā)深度優(yōu)先遍歷

p=p->nextarc; //找v的下一個相鄰點

}}7.3圖的遍歷64/88DFS思路：vv1v2v3vm一步一步向前走，當(dāng)沒有可走的相鄰頂點時便回退。…7.3圖的遍歷65/88企業(yè)面試題：無向圖G=（VE），其中V={a,b,c,d,e,f}E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}對該圖進行深度優(yōu)先排序，得到的頂點序列正確的是（）。

A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，babcdef用R表示回退一次A.a,a→b,b→e,e→d,不應(yīng)該到cB.a,a→c,c→f,f→d,不應(yīng)該到eC.a,a→e,e→b,R,e→d,不應(yīng)該到cD.a,a→e,e→d,d→f,f→c,R,R,R,e→b√7.3圖的遍歷66/88訪問頂點v；訪問頂點v的所有未被訪問過的相鄰點，假設(shè)訪問次序是vi1，vi2，…，vit。按vi1，vi2，…，vit的次序，訪問每個頂點的所有未被訪問過的相鄰點，直到圖中所有和初始點v有路徑相通的頂點都被訪問過為止。7.3.2廣度優(yōu)先遍歷算法廣度優(yōu)先遍歷（BreadthFirstSearch，簡稱BFS）：順序一致，用隊列實現(xiàn)7.3圖的遍歷67/88例如，對于圖7.8(a)的鄰接表，從頂點0出發(fā)的廣度優(yōu)先遍歷序列是0、1、3、2、4。v01131∧v10121∧v2113141∧v3012141∧v42131∧頭結(jié)點邊結(jié)點012347.3圖的遍歷68/88實現(xiàn)廣度優(yōu)先搜索的算法如下：voidBFS(AdjGraph*G,intvi){inti,v,visited[MAXVEX];

ArcNode*p;intQu[MAXVEX],front=0,rear=0; //定義一個循環(huán)隊列Qufor(i=0;i<G->n;i++)visited[i]=0; //visited數(shù)組置初值0printf("%d",vi); //訪問初始頂點visited[vi]=1;rear=(rear=1)%MAXVEX;Qu[rear]=vi; //初始頂點進隊while(front!=rear) //隊不為空時循環(huán){front=(front+1)%MAXVEX;

v=Qu[front]; //出隊頂點v

p=G->adjlist[v].firstarc; //查找v的第一個相鄰點

while(p!=NULL)

//查找v的所有相鄰點

{if(visited[p->adjvex]==0) //未訪問過則訪問之

{printf("%d",p->adjvex); //訪問該點并進隊visited[p->adjvex]=1;rear=(rear+1)%MAXVEX;Qu[rear]=p->adjvex;

}p=p->nextarc;

//查找v的下一個相鄰點

}

}}7.3圖的遍歷69/88BFS思路：vi一圈一圈向外走。7.3圖的遍歷70/887.3.3圖遍歷算法的應(yīng)用

【例7.8】假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，判斷無向圖G是否連通。若連通則返回1；否則返回0。先給visited[]數(shù)組置初值0。然后從0頂點開始遍歷該圖。在一次遍歷之后，若所有頂點i的visited[i]均為1，則該圖是連通的；否則不連通。7.3圖的遍歷采用某種遍歷方法判斷無向圖G是否連通。這里用深度優(yōu)先遍歷方法。71/88intConnect(AdjGraph*G) //判斷無向圖G的連通性{inti,flag=1;

DFS(G,0);

//調(diào)用DFS算法,從頂點0開始深度優(yōu)先遍歷

for(i=0;i<G->n;i++){if(visited[i]==0)

{flag=0;

break;

}}

returnflag;}7.3圖的遍歷72/88

【例7.9】假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法判斷頂點u到頂點v（u≠v）之間是否有簡單路徑。先置全局visited數(shù)組的所有元素值為0。從頂點u出發(fā)進行深度優(yōu)先遍歷，置visited[u]=1；找到頂點u的一個未訪問過的相鄰點u1，置visited[u1]=1；找到頂點u1的一個未訪問過的相鄰點u2，置visited[u2]=1；以此類推。當(dāng)找到的某個未訪問過的相鄰點un=v時，說明頂點u到v有一條簡單路徑，返回1。當(dāng)整個遍歷中都沒有找到頂點v，說明u到v沒有路徑，返回0。7.3圖的遍歷采用深度優(yōu)先遍歷思路設(shè)計求解算法HasaPath(G，u，v)。73/88intvisited[MAXVEX]; //全局?jǐn)?shù)組intHasaPath(AdjGraph*G,intu,intv){ArcNode*p;intw;visited[u]=1;p=G->adjlist[u].firstarc;//p指向u的第一個相鄰點while(p!=NULL){w=p->adjvex; //相鄰點的編號為wif(w==v) //找到頂點v后返回1return1;if(visited[w]==0) //若頂點w沒有訪問過{if(HasaPath(G,w,v)) //從w出發(fā)進行深度優(yōu)先遍歷return1; //若從w出發(fā)找到頂點v返回1}p=p->nextarc; //p指向下一個相鄰點}return0; //沒有找到頂點v，返回0}7.3圖的遍歷74/88從遞歸算法設(shè)計的角度求解本問題intvisited[MAXVEX]; //全局?jǐn)?shù)組intHasaPath1(AdjGraph*G,intu,intv){ArcNode*p;intw;

if(u==v)return1;

//找到頂點v后返回1visited[u]=1;p=G->adjlist[u].firstarc; //p指向u的第一個相鄰點while(p!=NULL){w=p->adjvex; //相鄰點的編號為wif(visited[w]==0) //若頂點w沒有訪問過{if(HasaPath1(G,w,v))//從w出發(fā)進行深度優(yōu)先遍歷return1; //若從w出發(fā)找到頂點v返回1}p=p->nextarc; //p指向下一個相鄰點}return0; //沒有找到頂點v，返回0}7.3圖的遍歷75/88

【例7.10】假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法求頂點u到頂點v（u≠v）之間的一條簡單路徑（假設(shè)兩頂點之間存在一條或多條簡單路徑）。

7.3圖的遍歷76/88采用深度優(yōu)先遍歷思路設(shè)計求解算法FindaPath(G，u，v，path，d)，其中用path[0..d]存放圖中從頂點u到v的一條簡單路徑，初始時數(shù)組path為空，d為-1。先置visited數(shù)組的所有元素值為0。從頂點u開始遍歷，置visited[u]=1，…。7.3圖的遍歷當(dāng)找到的某個未訪問過的鄰接點un=v時，說明找到了頂點u到v的一條簡單路徑，輸出path中頂點序列并返回。f(G,u,v,…)f(G,u1,v,…)f(G,v,v,…)…找不到未訪問的相鄰頂點77/88voidFindaPath(AdjGraph*G,intu,intv,intpath[],intd){ArcNode*p;intw,i;

visited[u]=1;

d++;path[d]=u; //頂點u加入到路徑中

if(u==v) //找到一條路徑

{for(i=0;i<=d;i++) //輸出找到一條路徑并返回

printf("%d",path[i]);

printf("\n");

return;

}

p=G->adjlist[u].firstarc; //p指向u的第一個相鄰點

while(p!=NULL)

{w=p->adjvex; //相鄰點的編號為w

if(visited[w]==0)

FindaPath(G,w,v,path,d);

//遞歸調(diào)用

p=p->nextarc; //p指向下一個相鄰點}}7.3圖的遍歷78/88

【例7.11】假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法求頂點u到頂點v（u≠v）之間的所有簡單路徑（假設(shè)兩頂點之間存在一條或多條簡單路徑）。7.3圖的遍歷79/88采用帶回溯DFS設(shè)計求解算法FindallPath(G,u,v,path,d)。先置visited數(shù)組的所有元素值為0。從頂點u開始，置visited[u]=1，…。7.3圖的遍歷當(dāng)找到的某個未訪問過的鄰接點un=v，說明path中存放的是頂點u到v的一條簡單路徑，輸出path。每次輸出的path構(gòu)成頂點u到v的全部簡單路徑中的一條，所有輸出的path構(gòu)成頂點u到v的全部簡單路徑。f(G,u,v,…)f(G,u1,v,…)f(G,v,v,…)…visited[v]=0找不到未訪問的相鄰頂點80/88voidFindallPath(AdjGraph*G,intu,intv,intpath[],intd){ArcNode*p;intw,i;

visited[u]=1;

d++;path[d]=u; //頂點u加入到路徑中

if(u==v)

//找到一條簡單路徑{for(i=0;i<=d;i++) //輸出找到一條路徑并返回

printf("%d",path[i]);

printf("\n");

visited[u]=0;

//回溯找所有簡單路徑

}else

{p=G->adjlist[u].firstarc; //