第6章

圖主講教師：張彬連吉首大學(xué)6.1知識(shí)簡(jiǎn)介

圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為G=（V，E），V表示圖G中頂點(diǎn)的集合，E表示圖G中邊的集合。根據(jù)圖的邊是否有無(wú)方向，將圖分為有向圖和無(wú)向圖。如果圖的任意兩個(gè)頂點(diǎn)之間的邊是無(wú)向的，則稱(chēng)該圖為無(wú)向圖。如果無(wú)向圖的邊是帶權(quán)值的，則稱(chēng)為無(wú)向網(wǎng)。如果圖的任意兩個(gè)頂點(diǎn)之間的邊是有向的，這樣的邊稱(chēng)為弧，稱(chēng)這樣的圖為有向圖。如果有向圖的弧是帶權(quán)值的，則稱(chēng)為有向網(wǎng)。6.1.1圖的定義6.1知識(shí)簡(jiǎn)介

圖有兩種典型的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣存儲(chǔ)結(jié)構(gòu)和鄰接表存儲(chǔ)結(jié)構(gòu)。6.1.2圖的存儲(chǔ)6.1知識(shí)簡(jiǎn)介1、鄰接矩陣存儲(chǔ)結(jié)構(gòu)6.1.2圖的存儲(chǔ)

鄰接矩陣表示法是用一個(gè)頂點(diǎn)表和一個(gè)鄰接矩陣來(lái)存儲(chǔ)圖的方法。頂點(diǎn)表用來(lái)記錄各個(gè)頂點(diǎn)的信息。鄰接矩陣是用來(lái)存儲(chǔ)各個(gè)頂點(diǎn)之間關(guān)系的矩陣。設(shè)圖G(V，E)是具有n個(gè)頂點(diǎn)的圖，則圖的鄰接矩陣是一個(gè)二維數(shù)組G.arcs[n][n]，定義為，如果頂點(diǎn)i和頂點(diǎn)j之間有邊或弧，則值為1，否則為0。G.arcs[i][j]表示如下：

6.1知識(shí)簡(jiǎn)介6.1.2圖的存儲(chǔ)

下圖顯示了一個(gè)無(wú)向圖及其鄰接矩陣。

無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的矩陣，圖中頂點(diǎn)i的度等于鄰接矩陣中對(duì)應(yīng)的第i行(列)中1的個(gè)數(shù)，鄰接矩陣中所有元素之和等于無(wú)向圖邊的2倍。1、鄰接矩陣存儲(chǔ)結(jié)構(gòu)6.1知識(shí)簡(jiǎn)介

下圖顯示了一個(gè)有向圖及其鄰接矩陣。

有向圖的鄰接矩陣可能是不對(duì)稱(chēng)的。圖中頂點(diǎn)i的出度等于鄰接矩陣中第i行元素之和，頂點(diǎn)的入度等于鄰接矩陣中第i列元素之和。鄰接矩陣中所有元素之和等于有向圖中弧的個(gè)數(shù)。1、鄰接矩陣存儲(chǔ)結(jié)構(gòu)6.1.2圖的存儲(chǔ)6.1知識(shí)簡(jiǎn)介

為了表示一個(gè)圖，應(yīng)該描述的信息有頂點(diǎn)信息表、頂點(diǎn)個(gè)數(shù)、邊的個(gè)數(shù)、頂點(diǎn)之間的關(guān)系，而鄰接矩陣主要表示頂點(diǎn)之間的關(guān)系。

用鄰接矩陣表示圖的定義如下：#defineMAXINT32767//表示極大值，即∞#defineMAXVNUM100//最大頂點(diǎn)數(shù)typedefstruct{VerTexTypevexs[MAXVNUM];//頂點(diǎn)表ArcTypearcs[MAXVNUM][MAXVNUM];//鄰接矩陣intvexNum； //頂點(diǎn)數(shù)intarcNum;//邊或弧數(shù)}AMGraph;1、鄰接矩陣存儲(chǔ)結(jié)構(gòu)6.1.2圖的存儲(chǔ)6.1知識(shí)簡(jiǎn)介6.1.2圖的存儲(chǔ)

如果用鄰接矩陣存儲(chǔ)網(wǎng)，則鄰接矩陣中元素的值用權(quán)值或無(wú)窮表示。如果兩個(gè)頂點(diǎn)之間有邊則對(duì)應(yīng)鄰接矩陣中的值為該邊的權(quán)值，如果沒(méi)有邊則值為無(wú)窮。

鄰接矩陣的空間復(fù)雜度為O(n2)，其中n為頂點(diǎn)個(gè)數(shù)。1、鄰接矩陣存儲(chǔ)結(jié)構(gòu)6.1知識(shí)簡(jiǎn)介

鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鄰接表表示法主要包括兩個(gè)部分：邊表和表頭結(jié)點(diǎn)表。邊表是對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，把與該頂點(diǎn)鄰接的頂點(diǎn)放在這個(gè)鏈表中。表頭結(jié)點(diǎn)表是用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)圖中頂點(diǎn)信息以及與該頂點(diǎn)對(duì)應(yīng)邊表第一個(gè)結(jié)點(diǎn)的地址。

表頭結(jié)點(diǎn)表是由表頭結(jié)點(diǎn)組成。表頭結(jié)點(diǎn)包括兩個(gè)部分：數(shù)據(jù)域和鏈域，數(shù)據(jù)域用來(lái)存儲(chǔ)頂點(diǎn)信息，鏈域用來(lái)指向邊表的第一個(gè)結(jié)點(diǎn)。

邊表由表示頂點(diǎn)間關(guān)系的邊結(jié)點(diǎn)組成。邊結(jié)點(diǎn)包括三個(gè)部分：鄰接點(diǎn)域、數(shù)據(jù)域和鏈域。鄰接點(diǎn)域用來(lái)表示頂點(diǎn)的某個(gè)鄰接點(diǎn)在圖中的位置。數(shù)據(jù)域用來(lái)存儲(chǔ)與邊相關(guān)的信息，如權(quán)值。鏈域用來(lái)指向與該頂點(diǎn)鄰接的下一條邊或弧的結(jié)點(diǎn)。6.1.2圖的存儲(chǔ)2、鄰接表存儲(chǔ)結(jié)構(gòu)6.1知識(shí)簡(jiǎn)介下圖為一個(gè)無(wú)向圖及其鄰接表表示。

無(wú)向圖某個(gè)頂點(diǎn)的度等于該頂點(diǎn)對(duì)應(yīng)單鏈表中結(jié)點(diǎn)個(gè)數(shù)，鏈表中所有結(jié)點(diǎn)的個(gè)數(shù)等于無(wú)向圖邊的2倍。6.1.2圖的存儲(chǔ)2、鄰接表存儲(chǔ)結(jié)構(gòu)6.1知識(shí)簡(jiǎn)介下圖為一個(gè)有向圖及其鄰接表表示。

有向圖中某個(gè)頂點(diǎn)的出度等于鄰接表中對(duì)應(yīng)單鏈表中結(jié)點(diǎn)個(gè)數(shù)，鏈表中所有結(jié)點(diǎn)的個(gè)數(shù)等于有向圖弧的個(gè)數(shù)。6.1.2圖的存儲(chǔ)2、鄰接表存儲(chǔ)結(jié)構(gòu)6.1知識(shí)簡(jiǎn)介用鄰接表表示圖的定義如下：#defineMAXVNUM100//最大頂點(diǎn)數(shù)typedefstructArcNode//邊結(jié)點(diǎn){intadjvex;//該邊所依附的另一個(gè)頂點(diǎn)的序號(hào)structArcNode*nextarc;

//指向下一條邊的指針OtherInfoinfo;//邊（或?。┫嚓P(guān)的信息}ArcNode;typedefstructVNode//表頭結(jié)點(diǎn){ VerTexTypedata;//頂點(diǎn)信息ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的邊}VNode,AdjList[MAXVNUM];//AdjList表示鄰接表類(lèi)型6.1.2圖的存儲(chǔ)2、鄰接表存儲(chǔ)結(jié)構(gòu)6.1知識(shí)簡(jiǎn)介typedefstruct{AdjListvertices;//鄰接表intvexNum;//頂點(diǎn)個(gè)數(shù)intarcNum;//邊或弧的個(gè)數(shù)}ALGraph;//鄰接表表示如果用鄰接表存儲(chǔ)網(wǎng)，則在邊結(jié)點(diǎn)中數(shù)據(jù)域info存儲(chǔ)對(duì)應(yīng)邊或弧的權(quán)值。鄰接表的空間復(fù)雜度為O(n+e)，n為頂點(diǎn)個(gè)數(shù)，e為邊個(gè)數(shù)。用鄰接表表示圖的定義如下：6.1.2圖的存儲(chǔ)2、鄰接表存儲(chǔ)結(jié)構(gòu)6.1知識(shí)簡(jiǎn)介6.1.3圖的遍歷1、深度優(yōu)先遍歷

圖的深度優(yōu)先搜索遍歷（簡(jiǎn)稱(chēng)DFS）類(lèi)似于樹(shù)的先序遍歷，是樹(shù)的先序遍歷的推廣。對(duì)于一個(gè)連通圖，深度優(yōu)先遍歷的過(guò)程如下：

第一步，從圖中某個(gè)頂點(diǎn)v出發(fā)，訪(fǎng)問(wèn)這個(gè)起始頂點(diǎn)v。

第二步，找到剛訪(fǎng)問(wèn)頂點(diǎn)的一個(gè)沒(méi)有訪(fǎng)問(wèn)的鄰接點(diǎn)w，以w為新的起始點(diǎn)對(duì)圖進(jìn)行深度優(yōu)先遍歷，直到剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)所有鄰接點(diǎn)都被訪(fǎng)問(wèn)為止。

第三步，返回前一個(gè)訪(fǎng)問(wèn)過(guò)且仍有未被訪(fǎng)問(wèn)的鄰接點(diǎn)的頂點(diǎn)，找到該頂點(diǎn)的一個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)，訪(fǎng)問(wèn)該頂點(diǎn)。

重復(fù)第二步和第三步，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)，搜索結(jié)束。6.1知識(shí)簡(jiǎn)介6.1.3圖的遍歷1、深度優(yōu)先遍歷

訪(fǎng)問(wèn)過(guò)程為了避免頂點(diǎn)重復(fù)訪(fǎng)問(wèn)，設(shè)置訪(fǎng)問(wèn)標(biāo)志visited[MAXVNUM]，數(shù)組的初始值都為false，表示開(kāi)始時(shí)所有的頂點(diǎn)都沒(méi)有被訪(fǎng)問(wèn)。當(dāng)訪(fǎng)問(wèn)某個(gè)頂點(diǎn)后，將該頂點(diǎn)對(duì)應(yīng)的visited值設(shè)置為true，表示該頂點(diǎn)已被訪(fǎng)問(wèn)。此遍歷的特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索。

對(duì)于非連通圖，從某個(gè)頂點(diǎn)出發(fā)遍歷后，圖中一定還有頂點(diǎn)未被訪(fǎng)問(wèn)，需要從圖中另選一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作為起點(diǎn)，重復(fù)上述深度優(yōu)先搜索過(guò)程，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)為止。

注意上述深度優(yōu)先遍歷的過(guò)程第二步，以w為新的起始點(diǎn)對(duì)圖進(jìn)行深度優(yōu)先遍歷。因此，深度優(yōu)先遍歷在一般情況下可用遞歸方式實(shí)現(xiàn)。

6.1知識(shí)簡(jiǎn)介6.1.3圖的遍歷2、廣度優(yōu)先遍歷

廣度優(yōu)先遍歷（簡(jiǎn)稱(chēng)BFS）類(lèi)似于樹(shù)的層次遍歷。對(duì)于一個(gè)連通圖，廣度優(yōu)先遍歷過(guò)程為：

第一步，從圖中某個(gè)頂點(diǎn)v出發(fā)，訪(fǎng)問(wèn)頂點(diǎn)v。

第二步，依次訪(fǎng)問(wèn)頂點(diǎn)v的各個(gè)未被訪(fǎng)問(wèn)過(guò)鄰接點(diǎn)。

第三步，分別從這些鄰接點(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)。

重復(fù)第三步，直到圖中所有已被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪(fǎng)問(wèn)到。6.1知識(shí)簡(jiǎn)介6.1.3圖的遍歷2、廣度優(yōu)先遍歷

在進(jìn)行廣度優(yōu)先搜索遍歷時(shí)，先訪(fǎng)問(wèn)的頂點(diǎn)其鄰接點(diǎn)先被訪(fǎng)問(wèn)。如果頂點(diǎn)i先于頂點(diǎn)j訪(fǎng)問(wèn)，則頂點(diǎn)i的未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)先于頂點(diǎn)j的未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)訪(fǎng)問(wèn)。因此，算法實(shí)現(xiàn)時(shí)需使用隊(duì)列來(lái)保存已被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)。

訪(fǎng)問(wèn)過(guò)程中為了避免頂點(diǎn)重復(fù)訪(fǎng)問(wèn)，設(shè)置訪(fǎng)問(wèn)標(biāo)志visited[MAXVNUM]，數(shù)組的初始值都為false，當(dāng)訪(fǎng)問(wèn)某個(gè)頂點(diǎn)后，將該頂點(diǎn)對(duì)應(yīng)的visited值設(shè)置為true，表示已訪(fǎng)問(wèn)。6.1知識(shí)簡(jiǎn)介6.1.3圖的遍歷2、廣度優(yōu)先遍歷

對(duì)于非連通圖，從某個(gè)頂點(diǎn)出發(fā)遍歷后，圖中一定還有頂點(diǎn)未被訪(fǎng)問(wèn)，需要從圖中另選一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作為起點(diǎn)，重復(fù)上述廣度優(yōu)先搜索過(guò)程，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)為止。

圖的遍歷過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程。6.2實(shí)驗(yàn)?zāi)康?/p>

通過(guò)本章的實(shí)驗(yàn)，加深對(duì)圖的鄰接矩陣、鄰接表兩種存儲(chǔ)方式以及深度優(yōu)先搜索、廣度優(yōu)先搜索等知識(shí)的理解，培養(yǎng)學(xué)生用圖結(jié)構(gòu)解決實(shí)際問(wèn)題的能力，同時(shí)鍛煉學(xué)生實(shí)際編程和算法設(shè)計(jì)的能力。6.3實(shí)驗(yàn)范例

用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)建立一個(gè)無(wú)向圖。6.3.1范例16.3實(shí)驗(yàn)范例1、問(wèn)題分析6.3.1范例1

采用鄰接矩陣存儲(chǔ)無(wú)向圖時(shí)，需要知道頂點(diǎn)數(shù)、邊數(shù)和邊信息，其中矩陣（二維數(shù)組）的大小由頂點(diǎn)數(shù)決定，邊信息將存儲(chǔ)在矩陣內(nèi)。

建立無(wú)向圖的算法步驟：

①輸入總頂點(diǎn)數(shù)vexNum和總邊數(shù)arcNum。

②依次輸入頂點(diǎn)的信息并將其存入頂點(diǎn)表vexs中。

③初始化鄰接矩陣，將每個(gè)元素初始化為0。

④構(gòu)造鄰接矩陣。依次輸入每條邊依附的頂點(diǎn)，確定兩個(gè)頂點(diǎn)在圖中的位置i、j，將鄰接矩陣中的第i行第j列和第j行第i列的值賦值1。6.3實(shí)驗(yàn)范例2、算法描述6.3.1范例1先定義無(wú)向圖存儲(chǔ)結(jié)構(gòu)如下：typedefstruct{VerTexTypevexs[MAXVNUM];//頂點(diǎn)表ArcTypearcs[MAXVNUM][MAXVNUM];//鄰接矩陣intvexNum; //頂點(diǎn)數(shù)intarcNum;//邊數(shù)}AMGraph;其中頂點(diǎn)類(lèi)型VerTexType和邊類(lèi)型ArcType可以定義成所需要的類(lèi)型。6.3實(shí)驗(yàn)范例2、算法描述6.3.1范例1

然后定義函數(shù)建立無(wú)向圖的鄰接矩陣，函數(shù)可以定義如下：StatusCreateUDG(AMGraph&G)｛inti,j,k;VerTexTypev1,v2;printf("輸入圖的頂點(diǎn)個(gè)數(shù)和邊數(shù):");scanf("%d%d",&G.vexNum,&G.arcNum);printf("輸入頂點(diǎn)信息：");fflush(stdin);//清空輸入緩沖區(qū)for(i=0;i<G.vexNum;i++){G.vexs[i]=getchar();

}6.3實(shí)驗(yàn)范例2、算法描述6.3.1范例1

然后定義函數(shù)建立無(wú)向圖的鄰接矩陣，函數(shù)可以定義如下：//初始化鄰接矩陣for(i=0;i<G.vexNum;i++)for(j=0;j<G.vexNum;j++)G.arcs[i][j]=0;printf("\n");printf("輸入邊的信息(v1,v2),每輸入一條邊回車(chē):\n");for(k=0;k<G.arcNum;k++){fflush(stdin);scanf("(%c,%c)",&v1,&v2);//查找兩個(gè)頂點(diǎn)的下標(biāo)i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=1;G.arcs[j][i]=1;}returnOK;}6.3實(shí)驗(yàn)范例2、算法描述6.3.1范例1

對(duì)于給出的一個(gè)頂點(diǎn)v，可以在頂點(diǎn)表中查找v對(duì)應(yīng)的下標(biāo)，設(shè)計(jì)LocateVex()函數(shù)如下：intLocateVex(AMGraphG,VerTexTypev)//查找頂點(diǎn)v在頂點(diǎn)表中的位置{inti;for(i=0;i<G.vexNum;i++){if(G.vexs[i]==v)returni;}return-1;//未找到，返回-1}6.3實(shí)驗(yàn)范例3、算法分析6.3.1范例1

執(zhí)行CreateUDG()函數(shù)的時(shí)間主要由用戶(hù)輸入數(shù)據(jù)的速度確定，用戶(hù)從鍵盤(pán)輸入數(shù)據(jù)需要的時(shí)間遠(yuǎn)遠(yuǎn)大于函數(shù)中其它語(yǔ)句的執(zhí)行時(shí)間。因此，計(jì)算這個(gè)函數(shù)的時(shí)間復(fù)雜度意義不大。6.3實(shí)驗(yàn)范例對(duì)范例1中建立的無(wú)向圖進(jìn)行深度優(yōu)先遍歷，輸出遍歷序列。6.3.2范例26.3實(shí)驗(yàn)范例1、問(wèn)題分析6.3.2范例2

假設(shè)從圖中第v個(gè)頂點(diǎn)出發(fā)對(duì)圖進(jìn)行深度優(yōu)先遍歷。先訪(fǎng)問(wèn)這個(gè)頂點(diǎn)，然后找到該頂點(diǎn)的一個(gè)沒(méi)有被訪(fǎng)問(wèn)的鄰接點(diǎn)，假設(shè)為第j個(gè)頂點(diǎn)，以第j個(gè)頂點(diǎn)為新的起始點(diǎn)對(duì)圖進(jìn)行深度優(yōu)先遍歷，直到頂點(diǎn)v的所有鄰接點(diǎn)都被訪(fǎng)問(wèn)為止。為了表示頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)，定義一個(gè)訪(fǎng)問(wèn)標(biāo)志數(shù)組visited1，如果第j個(gè)頂點(diǎn)沒(méi)有被訪(fǎng)問(wèn)過(guò)，則visited1[j]=0，否則visited1[j]=1。6.3實(shí)驗(yàn)范例2、算法描述6.3.2范例2

根據(jù)以上分析，先設(shè)置一個(gè)訪(fǎng)問(wèn)標(biāo)志數(shù)組visited1，然后從第v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷無(wú)向圖G?？稍O(shè)計(jì)深度優(yōu)先遍歷函數(shù)如下：intvisited1[MAXVNUM]={0};//定義成一個(gè)全局量voidDFSTraverse(AMGraphG,intv)

{//以v為起始頂點(diǎn)深度優(yōu)先遍歷無(wú)向圖Gintj;printf("%3c",G.vexs[v]);visited1[v]=1;//頂點(diǎn)v已被訪(fǎng)問(wèn)for(j=0;j<G.vexNum;j++)

{if(G.arcs[v][j]==1&&visited1[j]==0)//第j個(gè)頂點(diǎn)與v相鄰且沒(méi)有被訪(fǎng)問(wèn)DFSTraverse(G,j);//從頂點(diǎn)j出發(fā)深度優(yōu)先遍歷}}6.3實(shí)驗(yàn)范例3、算法分析6.3.2范例2

采用鄰接矩陣存儲(chǔ)方式對(duì)圖進(jìn)行深度優(yōu)先遍歷時(shí)，查找一個(gè)頂點(diǎn)的鄰接頂點(diǎn)所需的時(shí)間為O(n)，需要對(duì)n個(gè)頂點(diǎn)的鄰接頂點(diǎn)進(jìn)行查找，因此該時(shí)間復(fù)雜度為O(n2)。6.3實(shí)驗(yàn)范例

對(duì)范例1中建立的無(wú)向圖進(jìn)行廣度優(yōu)先遍歷，輸出遍歷序列。6.3.3范例36.3實(shí)驗(yàn)范例1、問(wèn)題分析6.3.3范例3

假設(shè)從圖中第v個(gè)頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷。先訪(fǎng)問(wèn)此頂點(diǎn)，然后訪(fǎng)問(wèn)該頂點(diǎn)的各個(gè)未曾訪(fǎng)問(wèn)的鄰接點(diǎn)w1，w2，…，wk。然后，依次從w1，w2，…，wk出發(fā)訪(fǎng)問(wèn)各自未被訪(fǎng)問(wèn)的鄰接點(diǎn)。重復(fù)上面的步驟，直到全部頂點(diǎn)都被訪(fǎng)問(wèn)為止。

廣度優(yōu)先遍歷需要借助隊(duì)列保存當(dāng)前已經(jīng)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，然后再訪(fǎng)問(wèn)這些頂點(diǎn)的鄰接點(diǎn)。為了表示頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)，定義一個(gè)訪(fǎng)問(wèn)標(biāo)志數(shù)組visited2，如果第j個(gè)頂點(diǎn)沒(méi)有被訪(fǎng)問(wèn)過(guò)，則visited2[j]=0，否則visited2[j]=1。6.3實(shí)驗(yàn)范例2、算法描述6.3.3范例3

根據(jù)以上分析，先設(shè)置一個(gè)訪(fǎng)問(wèn)標(biāo)志數(shù)組，然后從第v個(gè)頂點(diǎn)出發(fā)廣度優(yōu)先遍歷無(wú)向圖G。可設(shè)計(jì)廣度優(yōu)先遍歷函數(shù)BFSTraverse()如下：voidBFSTraverse(AMGraphG,intv)//以頂點(diǎn)v為起始頂點(diǎn)廣度優(yōu)先遍歷圖G{

intu,j;SqQueueQ;intvisited2[MAXVNUM]={0};

printf("%3c",G.vexs[v]);//訪(fǎng)問(wèn)起始頂點(diǎn)

visited2[v]=1;//將起始頂點(diǎn)設(shè)值已訪(fǎng)問(wèn)標(biāo)志

InitQueue(Q);//初始化隊(duì)列

EnQueue(Q,v);//將被訪(fǎng)問(wèn)頂點(diǎn)入隊(duì)6.3實(shí)驗(yàn)范例2、算法描述6.3.3范例3

根據(jù)以上分析，先設(shè)置一個(gè)訪(fǎng)問(wèn)標(biāo)志數(shù)組，然后從第v個(gè)頂點(diǎn)出發(fā)廣度優(yōu)先遍歷無(wú)向圖G?？稍O(shè)計(jì)廣度優(yōu)先遍歷函數(shù)BFSTraverse()如下：while(!QueueEmpty(Q)){DeQueue(Q,u);//隊(duì)頭元素出隊(duì)for(j=0;j<G.vexNum;j++){//找到頂點(diǎn)u的沒(méi)有被訪(fǎng)問(wèn)的鄰接點(diǎn)，訪(fǎng)問(wèn)并入隊(duì)if(G.arcs[u][j]==1&&visited2[j]==0){printf("%3c",G.vexs[j]);visited2[j]=1;

EnQueue(Q,j);}

}

}}6.3實(shí)驗(yàn)范例

前面三個(gè)函數(shù)加上隊(duì)列的基本操作，最后三個(gè)案例的源代碼如下：#include<stdio.h>#include<stdlib.h>#defineMAXVNUM100//最大頂點(diǎn)數(shù)#defineMAXQSIZE100#defineOK1#defineERROR0typedefcharVerTexType;typedefintArcType;typedefintStatus;//定義隊(duì)列typedefintQElemType;2、算法描述6.3.3范例3typedefstruct{QElemType*base;intfront;intrear;}SqQueue;6.3實(shí)驗(yàn)范例

前面三個(gè)函數(shù)加上隊(duì)列的基本操作，最后三個(gè)案例的源代碼如下：2、算法描述6.3.3范例3//初始化隊(duì)列QStatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)returnERROR;Q.front=0;Q.rear=0;returnOK;}//將元素e入隊(duì)QStatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}6.3實(shí)驗(yàn)范例

前面三個(gè)函數(shù)加上隊(duì)列的基本操作，最后三個(gè)案例的源代碼如下：2、算法描述6.3.3范例3//將隊(duì)列Q的對(duì)頭元素出隊(duì)，并用e返回出隊(duì)元素StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}//判斷隊(duì)列Q是否為空intQueueEmpty(SqQueueQ){if(Q.front==Q.rear)return1;elsereturn0;}6.3實(shí)驗(yàn)范例

前面三個(gè)函數(shù)加上隊(duì)列的基本操作，最后三個(gè)案例的源代碼如下：2、算法描述6.3.3范例3//加上建立圖、深度優(yōu)先遍歷和廣度優(yōu)先遍歷三個(gè)函數(shù)的定義//主函數(shù)intmain(){AMGraphG;CreateUDG(G);printf("深度優(yōu)先遍歷序列為:");DFSTraverse(G,0);printf("\n");printf("廣度優(yōu)先遍歷序列為:");BFSTraverse(G,0);return0;}6.3實(shí)驗(yàn)范例3、算法分析6.3.3范例3

采用鄰接矩陣存儲(chǔ)方式對(duì)圖進(jìn)行廣度優(yōu)先遍歷時(shí)，查找一個(gè)頂點(diǎn)的鄰接頂點(diǎn)所需的時(shí)間為O(n)，需要對(duì)n個(gè)頂點(diǎn)的鄰接頂點(diǎn)進(jìn)行查找，因此該時(shí)間復(fù)雜度為O(n2)。6.4實(shí)驗(yàn)任務(wù)完成下列任務(wù)，并分析各算法的時(shí)間復(fù)雜度。任務(wù)1：用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)建立一個(gè)無(wú)向圖。任務(wù)2：在任務(wù)1建立的無(wú)向圖鄰接表的基礎(chǔ)上，對(duì)圖進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列，并分析算法的時(shí)間復(fù)雜度。任務(wù)3（擴(kuò)展題，選做）：用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)建立一個(gè)連通網(wǎng)，并構(gòu)造該網(wǎng)的最小生成樹(shù)。6.4實(shí)驗(yàn)任務(wù)完成下列任務(wù)，并分析各算法的時(shí)間復(fù)雜度。任務(wù)4（擴(kuò)展題，選做）：校園導(dǎo)航系統(tǒng)。

用無(wú)向圖表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱(chēng)、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求實(shí)現(xiàn)如下功能：

①

查詢(xún)各景點(diǎn)的相關(guān)信息。

②

查詢(xún)圖中任意兩個(gè)景點(diǎn)間的最短路徑。

③

查詢(xún)圖中任意兩個(gè)景點(diǎn)間的所有路徑。6.5任務(wù)提示用鄰接表表示法創(chuàng)建無(wú)向圖步驟如下：

①輸入總頂點(diǎn)數(shù)和總邊數(shù)。

②依次輸入點(diǎn)的信息存入頂點(diǎn)表中，使每個(gè)表頭結(jié)點(diǎn)的指針域初

始化為NULL。

③創(chuàng)建鄰接表：

輸入邊，確定邊所依附的兩個(gè)頂點(diǎn)的序號(hào)i和j；

生成兩個(gè)邊表結(jié)點(diǎn)，將兩個(gè)結(jié)點(diǎn)的數(shù)據(jù)域存入j和i，并將這兩個(gè)邊表結(jié)點(diǎn)分別插入vi和vj對(duì)應(yīng)的兩個(gè)邊鏈表的頭部。任務(wù)1提示6.5任務(wù)提示偽代碼描述如下：任務(wù)1提示StatusCreateUDG(ALGraph&G){//輸入總頂點(diǎn)數(shù)，總邊數(shù)cin>>G.vexNum>>G.arcNum;//輸入各點(diǎn)，構(gòu)造表頭結(jié)點(diǎn)表for(i=0;i<G.vexNum;++i){cin>>G.vertices[i].data;//輸入頂點(diǎn)值G.vertices[i].firstarc=NULL;//初始化表頭結(jié)點(diǎn)的指針域?yàn)镹ULL}6.5任務(wù)提示偽代碼描述如下：任務(wù)1提示StatusCreateUDG(ALGraph&G){for(k=0;k<G.arcNum;++k){//輸入各邊，構(gòu)造鄰接表cin>>v1>>v2; //輸入一條邊依附的兩個(gè)頂點(diǎn)i=LocateVex(G,v1);

j=LocateVex(G,v2);//找到頂點(diǎn)在頂點(diǎn)表中的下標(biāo)//生成一個(gè)新的邊結(jié)點(diǎn)*p1p1=newArcNode;p1->adjvex=j;//鄰接點(diǎn)序號(hào)為jp1->nextarc=G.vertices[i].firstarc;//將p1插入頂點(diǎn)vi的邊表頭部

G.vertices[i].firstarc=p1;6.5任務(wù)提示偽代碼描述如下：任務(wù)1提示StatusCreateUDG(ALGraph&G){for(k=0;k<G.arcNum;++k){//輸入各邊，構(gòu)造鄰接表//生成另一個(gè)對(duì)稱(chēng)的新的邊結(jié)點(diǎn)*p2

p2=newArcNode;

p2->adjvex=i;//鄰接點(diǎn)序號(hào)為ip2->nextarc=G.vertices[j].firstarc;//將新結(jié)點(diǎn)*p2插入頂點(diǎn)vj的邊表頭部

G.vertices[j].firstarc=p2;}

returnOK;}6.5任務(wù)提示

基于鄰接表存儲(chǔ)方式的遍歷與基于鄰接矩陣存儲(chǔ)方式的遍歷在找鄰接點(diǎn)方式上有所不同。在鄰接表中，某個(gè)頂點(diǎn)的所有鄰接點(diǎn)存儲(chǔ)在該頂點(diǎn)對(duì)應(yīng)的邊表中，對(duì)邊表進(jìn)行遍歷就可以找到頂點(diǎn)的所有鄰接點(diǎn)。任務(wù)2提示6.5任務(wù)提示基于鄰接表存儲(chǔ)方式深度優(yōu)先遍歷圖G的偽代碼描述如下：任務(wù)2提示voidDFS(ALGraphG,intv){//從第v個(gè)頂點(diǎn)出發(fā)對(duì)圖G進(jìn)行深度優(yōu)先遍歷cout<<G.vertices[i].data;//訪(fǎng)問(wèn)第v個(gè)頂點(diǎn)visited[v]=true;//設(shè)置已訪(fǎng)問(wèn)標(biāo)志

p=G.vertices[v].firstarc;//p指向v的邊鏈表的第一個(gè)邊結(jié)點(diǎn)while(p!=NULL)//依次檢查v的鄰接點(diǎn){w=p->adjvex;//w是v的鄰接點(diǎn)//如果w未訪(fǎng)問(wèn)，則遞歸調(diào)用DFSif(!visited[w])DFS(G,w); p=p->nextarc;//p指向下一個(gè)邊結(jié)點(diǎn)}}6.5任務(wù)提示基于鄰接表存儲(chǔ)方式廣度優(yōu)先遍歷圖G的偽代碼描述如下：任務(wù)2提示voidBFS(ALGraphG,intv)//從第v個(gè)頂點(diǎn)出發(fā)對(duì)圖G進(jìn)行廣度優(yōu)先遍歷{

cout<<G.vertices[v].data;//訪(fǎng)問(wèn)第v個(gè)頂點(diǎn)visited[v]=1;//設(shè)置已訪(fǎng)問(wèn)標(biāo)志InitQueue(Q);//初始化隊(duì)列QEnQueue(Q,v);//并將v入隊(duì)

while(!QueueEmpty(Q))//隊(duì)列非空

{DeQueue(Q,u);//隊(duì)頭元素出隊(duì)并賦給up=G.vertices[u].firstarc;//找到u的邊結(jié)點(diǎn)6.5任務(wù)提示基于鄰接表存儲(chǔ)方式廣度優(yōu)先遍歷圖G的偽代碼描述如下：任務(wù)2提示voidBFS(ALGraphG,intv)//從第v個(gè)頂點(diǎn)出發(fā)對(duì)圖G進(jìn)行廣度優(yōu)先遍歷{while(p!=NULL){w=p->adjvex;if(visited[w]==0)//w為u的尚未訪(fǎng)問(wèn)的鄰接頂點(diǎn){cout<<G.vertices[w].data;//訪(fǎng)問(wèn)第w個(gè)頂點(diǎn)visited[w]=1;//設(shè)置已訪(fǎng)問(wèn)標(biāo)志EnQueue(Q,w);//w進(jìn)隊(duì)}p=p->nextarc;//找下一個(gè)鄰接點(diǎn)

}}}6.5任務(wù)提示

如果連通圖是一個(gè)網(wǎng)絡(luò)，生成樹(shù)的各邊權(quán)值之和稱(chēng)為這棵生成樹(shù)的代價(jià)，稱(chēng)該網(wǎng)絡(luò)所有生成樹(shù)中權(quán)值最小的生成樹(shù)為最小代價(jià)生成樹(shù)，簡(jiǎn)稱(chēng)為最小生成樹(shù)。常見(jiàn)的構(gòu)造最小生成樹(shù)的算法有普里姆（Prim）算法和克魯斯卡爾(Kruskal)算法。兩種算法都是利用MST性質(zhì)構(gòu)造最小生成樹(shù)的算法。任務(wù)3提示MST性質(zhì)：假設(shè)N=(V，E)是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集，若(u，v)是一條具有最小權(quán)值（代價(jià)）的邊，其中u∈U、v∈V-U，則必存在一棵包含邊(u，v)的最小生成樹(shù)。6.5任務(wù)提示

實(shí)現(xiàn)克魯斯卡爾(Kruskal)算法一般采用邊集數(shù)組形式存儲(chǔ)網(wǎng)，而不是鄰接矩陣方式存儲(chǔ)，所以本題采用Prim算法。任務(wù)3提示

普里姆（Prim）算法的基本思想：假設(shè)網(wǎng)G=（V，E）是連通的，T=（U，TE）為要構(gòu)造的一棵最小生成樹(shù)，其中U是G上最小生成樹(shù)頂點(diǎn)的集合，TE是G上最小生成樹(shù)中邊的集合。開(kāi)始時(shí)U={u0}，TE={}。重復(fù)進(jìn)行如下操作：在所有u∈U，v∈V-U的邊（u,v）∈E中，選擇一條權(quán)最小的邊（u,v）并入TE中，同時(shí)將v并入U(xiǎn)，直到U=V為止。這時(shí)產(chǎn)生的TE中必有n-1條邊，T=（U，TE）是G的一棵最小生成樹(shù)。6.5任務(wù)提示算法實(shí)現(xiàn)過(guò)程中需引進(jìn)一個(gè)數(shù)組closedge，其定義如下：struct//定義從頂點(diǎn)集U到V-U的權(quán)值最小的邊的輔助數(shù)組{ArcTypelowcost;//存放最小邊上的權(quán)值VerTexTypeadjvex;//最小邊在集合U中的頂點(diǎn)}closedge[MAXVNUM];任務(wù)3提示

數(shù)組中的兩個(gè)成員adjvex和lowcost，分別用于存放最小邊在集合U中的頂點(diǎn)和最小邊上的權(quán)值。6.5任務(wù)提示

所有的頂點(diǎn)closedge[i].adjvex都已在U中。任務(wù)3提示

若closedge[k].lowcost=0，則表示下標(biāo)為k的頂點(diǎn)在U中；

若0＜closedge[k].lowcost＜∞，則下標(biāo)為k的頂點(diǎn)在V-U中，且(closedge[k].adjvex,vex[k])是與頂點(diǎn)vex[k]鄰接的且兩鄰接頂點(diǎn)分別在U和V-U的所有邊中權(quán)值最小的邊，其最小權(quán)值就是closedge[k].lowcost；

若closedge[k].lowcost=∞，則表示closedge[k].adjvex與頂點(diǎn)vex[k]之間沒(méi)有邊，用∞表示。6.5任務(wù)提示任務(wù)3提示基于鄰接矩陣存儲(chǔ)和closedge數(shù)組的Prim算法的實(shí)現(xiàn)步驟如下：

①首先將初始頂點(diǎn)u加入U(xiǎn)中，對(duì)其余的每一個(gè)頂點(diǎn)，將closedge中對(duì)應(yīng)的值初始化為該頂點(diǎn)到u的邊信息。

②循環(huán)vexNum－1次，做如下處理：從各組邊closedge中選出最小邊closedge[k]，輸出此邊；將k加入U(xiǎn)中；更新剩余的每組最小邊信息closedge[j]，對(duì)于V－U中的邊，新增加了一條從k到j(luò)的邊，如果新邊的權(quán)值比closedge[j].lowcost小，則將closedge[j].lowcost更新為新邊的權(quán)值。6.5任務(wù)提示

可以采用鄰接矩陣的方式對(duì)圖進(jìn)行存儲(chǔ)。需要查詢(xún)?nèi)我鈨蓚€(gè)景點(diǎn)的最短路徑，也就是圖中任何兩個(gè)頂點(diǎn)之間的最短路徑。求所有頂點(diǎn)之間的路徑可用Floyd算法。

可以基于深度優(yōu)先遍歷求任何兩個(gè)景點(diǎn)的所有路徑。任務(wù)4提示6.5任務(wù)提示（1）求所有頂點(diǎn)之間的最短路徑——Floyd算法任務(wù)4提示Floyd算法又稱(chēng)為插點(diǎn)法，是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法，與Dijkstra算法類(lèi)似。該算法名稱(chēng)以創(chuàng)始人之一、1978年圖靈獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德命名。

通過(guò)一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=[a(i,j)]n×n開(kāi)始，迭代地進(jìn)行n次更新，即由矩陣D(0)=A，按一個(gè)公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑長(zhǎng)度，稱(chēng)D(n)為圖的距離矩陣，同時(shí)還可引入一個(gè)后繼節(jié)點(diǎn)矩陣path來(lái)記錄兩點(diǎn)間的最短路徑。6.5任務(wù)提示（1）求所有頂點(diǎn)之間的最短路徑——Floyd算法任務(wù)4提示

在實(shí)現(xiàn)過(guò)程中需要引入兩個(gè)輔助的二維數(shù)組：二維數(shù)組Path[i][j]，存儲(chǔ)最短路徑上頂點(diǎn)vj的前一頂點(diǎn)的序號(hào)；二維數(shù)組D[i][j]，記錄頂點(diǎn)vi和vj之間的最短路徑長(zhǎng)度。6.5任務(wù)提示（1）求所有頂點(diǎn)之間的最短路徑——Floyd算法任務(wù)4提示算法步驟如下：

①將vi到vj的最短路徑長(zhǎng)度初始化，即D[i][j]=G.arcs[i][j]。

②進(jìn)行n次比較和更新。在vi和vj之間加入頂點(diǎn)v0，比較（vi，vj）和（vi，v0，vj）的路徑長(zhǎng)度，取其中較短者作為vi到vj的中間頂點(diǎn)序號(hào)不大于0的最短路徑。6.5任務(wù)提示（1）求所有頂點(diǎn)之間的最短路徑——Floyd算法任務(wù)4提示算法步驟如下：在vi和vj之間加入頂點(diǎn)v1，得到（vi，…，v1）和（v1，…，vj），其中（vi，…，v1）是從vi到v1的且中間頂點(diǎn)序號(hào)不大于0的最短路徑，（v1，…，vj）是從v1到vj的且中間頂點(diǎn)的序號(hào)不大于0的最短路徑。這兩個(gè)路徑已經(jīng)在上一步求出。比較（vi，…，v1，…，vj）與上一步求出的vi到vj的中間頂點(diǎn)序號(hào)不大于0的的路徑長(zhǎng)度，取其中較短者作為vi到vj的中間頂點(diǎn)序號(hào)不大于1的最短路徑。6.5任務(wù)提示（1）求所有頂點(diǎn)之間的最短路徑——Floyd算法任務(wù)4提示算法步驟如下：依次類(lèi)推，在vi和vj之間加入頂點(diǎn)vk，得到（vi，…，vk）和（vk，…，vj），其中（vi，…，vk）是從vi到vk的且中間頂點(diǎn)序號(hào)不大于k-1的最短路徑，（vk，…，vj）是從vk到vj的且中間頂點(diǎn)的序號(hào)不大于k-1的最短路徑。將（vi，…，vk，…，vj）和已經(jīng)得到的從vi到vj的且中間頂點(diǎn)序號(hào)不大于k-1的的路徑相比較，其長(zhǎng)度較短者便是vi到vj的中間頂點(diǎn)序號(hào)不大于k的最短路徑。經(jīng)過(guò)n次比較后，最后求得的必是從vi到vj的最短路徑。6.5任務(wù)提示（1）求所有頂點(diǎn)之間的最短路徑——Floyd算法任務(wù)4提示

圖中的所有頂點(diǎn)對(duì)vi和vj間的最短路徑長(zhǎng)度對(duì)應(yīng)一個(gè)n階方陣D。在上述n+1步中，D的值不斷變化，對(duì)應(yīng)一個(gè)n階方陣序列。n階方陣序列可定義為：D(-1)，D(0)，D(1)，…，D(k)，…，D(n-1)

其中，D(-1)[i][j]=G.arcs[i][j]，D(k)[i][j]=min{D(k-1)[i][j]，D(k-1)[i][k]+D(k-1)[k][j]}0≤k≤n-1。

顯然，D(1)[i][j]是從vi到vj的且中間頂點(diǎn)的序號(hào)不大于1的最短路徑的長(zhǎng)度；D(k)[i][j]是從vi到vj的且中間頂點(diǎn)的序號(hào)不大于k的最短路徑的長(zhǎng)度；D(n-1)[i][j]就是從vi到vj的最短路徑的長(zhǎng)度。6.5任務(wù)提示（1）求所有頂點(diǎn)之間的最短路徑——Floyd算法任務(wù)4提示算法的偽代碼描述如下：voidShortestPath_Floyd(AMGraphG){//所有頂點(diǎn)對(duì)初始化已知路徑長(zhǎng)度和距離for(i=0;i<G.vertexNum,i++)for(j=0;j<G.vertexNum;j++){D[i][j]=G.arcs[i][j];//i和j之間有邊，則j的前驅(qū)為i，否則為-1if(D[i][j]<MAXINT&&i!=j)Path[i][j]=i;elsePath[i][j]=-1;

}for(k=0;k<G.vertexNum;k++)for(i=0;i<G.vertexNum;i++)for(j=0;j<G.vertexNum;j++)//找到i和j之間更短路徑，此路徑經(jīng)過(guò)kif(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j];//更新路徑Path[i][j]=Path[k][j];//修改前驅(qū)}}6.5任務(wù)提示（1）求所有頂點(diǎn)之間的最短路徑——Floyd算法任務(wù)4提示

該算法的時(shí)間復(fù)雜度為O(n3)。6.5任務(wù)提示（2）求無(wú)向圖中任意兩個(gè)頂點(diǎn)的所有路徑算法任務(wù)4提示

該法基于圖的深度優(yōu)先遍歷。實(shí)現(xiàn)過(guò)程中使用棧和標(biāo)記數(shù)組為輔助。棧用來(lái)存儲(chǔ)正在搜索的路徑，棧底為源點(diǎn)。一個(gè)標(biāo)記數(shù)組用來(lái)標(biāo)記每一輪搜索過(guò)程中路徑上的頂點(diǎn)是否被訪(fǎng)問(wèn)（或者表示是否在棧中，避免回路的產(chǎn)生）。6.5任務(wù)提示（2）求無(wú)向圖中任意兩個(gè)頂點(diǎn)的所有路徑算法任務(wù)4提示利用深度優(yōu)先搜索獲取兩點(diǎn)間所有簡(jiǎn)單路徑的過(guò)程為：

給定一個(gè)無(wú)向網(wǎng)G的鄰接矩陣存儲(chǔ)方式，起始頂點(diǎn)v和目標(biāo)頂點(diǎn)w。輔助棧S和輔助標(biāo)記數(shù)組flag[]。開(kāi)始時(shí)將v入棧S，并將v對(duì)應(yīng)標(biāo)記改為已訪(fǎng)問(wèn)標(biāo)記。只要棧S不為空，獲得棧頂元素t，如果棧頂元素為目標(biāo)頂點(diǎn)w，則找到一條頂點(diǎn)v到頂點(diǎn)w的路徑，其路徑就在棧S中，輸出棧S中的所有元素，并將該頂點(diǎn)出棧，同時(shí)設(shè)置未訪(fǎng)問(wèn)標(biāo)記，回溯到上一個(gè)頂點(diǎn)。6.5任務(wù)提示（2）求無(wú)向圖中任意兩個(gè)頂點(diǎn)的所有路徑算法任務(wù)4提示利用深度優(yōu)先搜索獲取兩點(diǎn)間所有簡(jiǎn)單路徑的過(guò)程為：

如果棧頂元素不是目標(biāo)頂點(diǎn)w，則找到v的一個(gè)未訪(fǎng)問(wèn)的頂點(diǎn)i，以該頂點(diǎn)為起始頂點(diǎn)找到到目標(biāo)頂點(diǎn)w的路徑。如果該頂點(diǎn)的所有鄰接點(diǎn)都找完，這時(shí)將該頂點(diǎn)出棧，同時(shí)設(shè)置未訪(fǎng)問(wèn)標(biāo)記，回溯到上一個(gè)頂點(diǎn)。當(dāng)起始頂點(diǎn)的所有鄰接點(diǎn)都找完，棧為空，算法結(jié)束。6.5任務(wù)提示（2）求無(wú)向圖中任意兩個(gè)頂點(diǎn)的所有路徑算法任務(wù)4提示算法偽代碼描述如下：輔助棧S和輔助標(biāo)記數(shù)組flag[MAXVNUM]。voidDFS_AllPath(AMGraphG,VerTexTypev,VerTexTypew){s1=LocateVex(G,v);//找到頂點(diǎn)v的下標(biāo)Push(S,v);//將起始頂點(diǎn)入棧flag[s1]=1;//將其標(biāo)記為已訪(fǎng)問(wèn)標(biāo)記，也就是在棧中while(StackEmpty(S)!=1)//棧不為空{(diào)GetTop(S,t);//獲得當(dāng)前頂點(diǎn)s1=LocateVex(G,t);6.5任務(wù)提示（2）求無(wú)向圖中任意兩個(gè)頂點(diǎn)的所有路徑算法任務(wù)4提示算法偽代碼描述如下：輔助棧S和輔助標(biāo)記數(shù)組flag[MAXVNUM]。voidDFS_AllPath(AMGraphG,VerTexTypev,VerTexTypew){s1=LocateVex(G,t);if(t==w)//找到目標(biāo)結(jié)點(diǎn){printf("找到一條路徑：");printStack(S);printf("\n");//將頂點(diǎn)出棧，并設(shè)為未訪(fǎng)問(wèn)標(biāo)志Pop(S,x);s2=LocateVex(G,x);flag[s2]=0;break;

}6.5任務(wù)提示（2）求無(wú)向圖中任意兩個(gè)頂點(diǎn)的所有路徑算法任務(wù)4提示算法偽代碼描述如下：輔助棧S和輔助標(biāo)記數(shù)組flag[MAXVNUM]。voidDFS_AllPath(AMGraphG,VerTexTypev,VerTexTypew){else{for(i=0;i<G.vertexNum;i++){if(G.arcs[s1][i]!=MAXINT&&flag[i]==0)

{

//找到一個(gè)未訪(fǎng)問(wèn)的鄰接點(diǎn)

DFS_AllPath(G,G.vex[i],w);

}

}6.5任務(wù)提示（2）求無(wú)向圖中任意兩個(gè)頂點(diǎn)的所有路徑算法任務(wù)4提示算法偽代碼描述如下：輔助棧S和輔助標(biāo)記數(shù)組flag[MAXVNUM]。voidDFS_AllPath(AMGraphG,VerTexTypev,VerTexTypew){if(i==G.vertexNum)//當(dāng)其所有鄰接點(diǎn)都訪(fǎng)問(wèn)完{Pop(S,t);//將棧頂頂點(diǎn)出棧S2=LocateVex(G,t);flag[s2]=0;//設(shè)未訪(fǎng)問(wèn)標(biāo)記break;}}}}第7章

查找7.1知識(shí)簡(jiǎn)介

在數(shù)據(jù)結(jié)構(gòu)中，查找是計(jì)算機(jī)科學(xué)中的一個(gè)重要概念和操作，它是指在一組預(yù)先組織好的數(shù)據(jù)集合（稱(chēng)為查找表或查找結(jié)構(gòu)）中確定一個(gè)特定的數(shù)據(jù)元素（記錄或鍵值對(duì)）的過(guò)程。查找的目的通常是為了找到與給定關(guān)鍵字相匹配的數(shù)據(jù)元素。7.1.1查找1、查找表

查找表是由同一類(lèi)型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系，因此查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)，可以利用其他的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，如線(xiàn)性表、樹(shù)表和散列表等。7.1知識(shí)簡(jiǎn)介2、關(guān)鍵字

關(guān)鍵字是數(shù)據(jù)元素中的某個(gè)特定字段，用以區(qū)分不同的數(shù)據(jù)元素。主關(guān)鍵字通常是用來(lái)進(jìn)行查找的主要依據(jù)，而次關(guān)鍵字則可以用于輔助排序或進(jìn)一步細(xì)化搜索條件。7.1.1查找3、查找方法

按數(shù)據(jù)結(jié)構(gòu)組織方式可以分為：線(xiàn)性表的查找、樹(shù)表的查找和哈希表的查找。

線(xiàn)性表的查找：采用線(xiàn)性表作為查找表的組織形式，在線(xiàn)性表中查找指定元素主要方法有：順序查找、折半查找（也稱(chēng)為二分查找，僅限于有序線(xiàn)性表）、分塊查找。7.1知識(shí)簡(jiǎn)介7.1.1查找

樹(shù)表的查找：采用樹(shù)作為查找表的組織形式，查找操作主要依賴(lài)于樹(shù)的類(lèi)型和特性，查找方法有：二叉排序樹(shù)（二叉查找樹(shù)）、B樹(shù)、AVL樹(shù)、紅黑樹(shù)等，根據(jù)結(jié)點(diǎn)的關(guān)鍵字值進(jìn)行遞歸搜索。

哈希表的查找：哈希表（HashTable）是一種高效的數(shù)據(jù)結(jié)構(gòu)，它通過(guò)使用哈希函數(shù)將關(guān)鍵字映射到一個(gè)固定大小的數(shù)組中，從而實(shí)現(xiàn)快速查找、插入和刪除操作。4、查找性能指標(biāo)

查找長(zhǎng)度：查找過(guò)程中實(shí)際需要對(duì)比的關(guān)鍵字次數(shù)。

平均查找長(zhǎng)度(ASL)：為了確定數(shù)據(jù)元素在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，稱(chēng)為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。它是衡量查找算法效率的重要標(biāo)準(zhǔn)。7.1知識(shí)簡(jiǎn)介

在線(xiàn)性表的查找中，順序查找既適用于線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，用適用于線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，折半查找要求線(xiàn)性表必須是順序存儲(chǔ)結(jié)構(gòu)，分塊查找的表可以是順序存儲(chǔ)結(jié)構(gòu)也可以是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但索引表必須是順序存儲(chǔ)結(jié)構(gòu)。7.1.2線(xiàn)性表的查找

查找表采用順序存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)描述為：//數(shù)據(jù)元素類(lèi)型typedefstruct{KeyTypekey;//關(guān)鍵字域InfoTypeotherinfo;}ElemType;typedefstruct{ElemType*R;//存儲(chǔ)空間基地址intlength;//當(dāng)前長(zhǎng)度}SSTable;7.1知識(shí)簡(jiǎn)介7.1.3樹(shù)表的查找

樹(shù)表的查找主要掌握二叉排序樹(shù)。二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若右子結(jié)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；左右子樹(shù)又分別是二叉排序樹(shù)。

采用二叉鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)二叉排序樹(shù)，二叉鏈表存儲(chǔ)表示如下：//數(shù)據(jù)元素類(lèi)型typedefstruct{KeyTypekey;//關(guān)鍵字項(xiàng)InfoTypeotherinfo;//其他數(shù)據(jù)項(xiàng)}ElemType;typedefstructBSTNode{ElemTypedata;structBSTNode*lchild;//左孩子指針

structBSTNode*rchild;//右孩子指針}BSTNode,*BSTree;7.2實(shí)驗(yàn)?zāi)康?/p>

通過(guò)本章的實(shí)驗(yàn)，深刻理解基于不同查找結(jié)構(gòu)的查找技術(shù)，在實(shí)際應(yīng)用中能夠靈活選擇或設(shè)計(jì)合適的查找方法，同時(shí)鍛煉學(xué)生實(shí)際編程和算法設(shè)計(jì)的能力。7.3實(shí)驗(yàn)范例學(xué)號(hào)姓名性別大學(xué)英語(yǔ)高等數(shù)學(xué)2023001AlanF93882023002DanieM75692023003PeterM56772023004BillF87902023005HelenM79862023006AmyF6875一個(gè)班有50個(gè)學(xué)生，每個(gè)學(xué)生的信息有學(xué)號(hào)、姓名、性別、大學(xué)英語(yǔ)成績(jī)和高等數(shù)學(xué)成績(jī)，學(xué)生信息如下表所示。要求根據(jù)輸入的學(xué)號(hào)查找學(xué)生的信息。7.3實(shí)驗(yàn)范例

順序查找（設(shè)置監(jiān)視哨）：根據(jù)輸入的n個(gè)學(xué)生的信息，建立順序表，并在順序表中用順序查找方法（帶監(jiān)視哨）查找與輸入的學(xué)號(hào)相同的學(xué)生信息，輸出該學(xué)生的所有信息。7.3.1范例17.3實(shí)驗(yàn)范例1、問(wèn)題分析7.3.1范例1

先需要定義順序表，順序表中每個(gè)元素用來(lái)存儲(chǔ)一個(gè)學(xué)生的信息，需要定義結(jié)構(gòu)體類(lèi)型，數(shù)據(jù)元素的類(lèi)型就是結(jié)構(gòu)體類(lèi)型。

然后初始化順序表，分配能放MAXSIZE+1學(xué)生信息的空間（下標(biāo)為0的單元用來(lái)存放哨兵），將順序表的長(zhǎng)度初始化為0。

接著建立長(zhǎng)度為n的順序表，輸入n個(gè)學(xué)生信息，將學(xué)生信息存入順序表中。這個(gè)過(guò)程和實(shí)驗(yàn)一的過(guò)程相同。輸入需要查找學(xué)生的學(xué)號(hào)，利用順序查找在順序表中查找和給定學(xué)號(hào)相同的學(xué)生。7.3實(shí)驗(yàn)范例1、問(wèn)題分析7.3.1范例1

順序查找（帶監(jiān)視哨）操作的基本步驟：

先將帶查找的關(guān)鍵字的值存入監(jiān)視哨中，監(jiān)視哨可設(shè)置在表頭，也可設(shè)置在表尾，這里我們將其設(shè)置在表頭。

接著從表中最后一個(gè)元素開(kāi)始，逆序掃描查找表，依次將掃描到的元素的學(xué)號(hào)與所給學(xué)號(hào)進(jìn)行比較，相等，返回該元素的下標(biāo)。由于將待查找的學(xué)號(hào)放在下標(biāo)為0的位置，如果元素不存在，當(dāng)比較到監(jiān)視哨時(shí)兩個(gè)學(xué)號(hào)相等，返回0，表示查找失敗。

由于順序表中的數(shù)據(jù)元素包含多個(gè)數(shù)據(jù)，輸入一個(gè)學(xué)生信息和輸出一個(gè)學(xué)生信息分別定義兩個(gè)函數(shù)來(lái)實(shí)現(xiàn)。7.3實(shí)驗(yàn)范例2、算法描述7.3.1范例1先定義順序查找表SSTable，定義如下：//數(shù)據(jù)元素類(lèi)型typedefstructStudent{charNo[8];//學(xué)號(hào)charname[16];//姓名charsex;//性別intenglish;//大學(xué)英語(yǔ)成績(jī)intmath;//高等數(shù)學(xué)成績(jī)}ElemType;//順序查找表typedefstruct{ElemType*R;//存儲(chǔ)空間基地址intlength;//當(dāng)前長(zhǎng)度}SSTable;7.3實(shí)驗(yàn)范例2、算法描述7.3.1范例1

順序查找表類(lèi)型定義好之后，可以初始化查找表ST。先新申請(qǐng)能存儲(chǔ)MAXSIZE+1個(gè)ElemType型數(shù)據(jù)的空間（下標(biāo)為0的單元用來(lái)存放哨兵），然后將查找表ST的初始長(zhǎng)度length設(shè)置為0。初始化查找表的函數(shù)可以定義如下：voidInitList(SSTable&ST){

//分配內(nèi)存單元，下標(biāo)為0的位置放哨兵

ST.R=(ElemType*)malloc((MAXSIZE+1)*sizeof(ElemType));

if(!ST.R)

exit(0);

ST.length=0;}7.3實(shí)驗(yàn)范例2、算法描述7.3.1范例1

接著設(shè)計(jì)函數(shù)用來(lái)建立長(zhǎng)度為n的查找表ST，輸入n個(gè)學(xué)生信息存入查找表ST中，將查找表當(dāng)前長(zhǎng)度length設(shè)置為n。在定義該函數(shù)之前定義函數(shù)用來(lái)輸入一個(gè)學(xué)生信息。輸入一個(gè)學(xué)生信息的函數(shù)定義如下：voidInputOneStu(ElemType&stu){fflush(stdin);//清空輸入緩沖區(qū)printf("學(xué)號(hào):");gets(stu.No);fflush(stdin);printf("姓名:");fflush(stdin);gets();printf("性別：");scanf("%c",&stu.sex);printf("大學(xué)英語(yǔ)成績(jī)：");scanf("%d",&stu.english);printf("高等數(shù)學(xué)成績(jī)：");scanf("%d",&stu.math);}7.3實(shí)驗(yàn)范例2、算法描述7.3.1范例1

在建立長(zhǎng)度為n的查找表函數(shù)中循環(huán)n次調(diào)用函數(shù)InputOneStu()用來(lái)輸入n個(gè)學(xué)生信息，函數(shù)可以定義如下：voidCreateSSTable(SSTable&ST,intn){inti;printf("輸入%d個(gè)學(xué)生信息：\n",n);for(i=1;i<=n;i++){InputOneStu(ST.R[i]);}ST.length=n;}7.3實(shí)驗(yàn)范例2、算法描述7.3.1范例1

設(shè)計(jì)查找函數(shù)，在查找表ST中查找學(xué)號(hào)等于stdNo的元素，找到則返回該元素的序號(hào)，否則返回0。函數(shù)可以定義如下：intSearch_Seq(SSTable&ST,char*stdNo){inti;strcpy(ST.R[0].No,stdNo);//設(shè)置哨兵for(i=ST.length;strcmp(ST.R[i].No,stdNo)!=0;i--);returni;}7.3實(shí)驗(yàn)范例2、算法描述7.3.1范例1

定義函數(shù)PrintStuInfo(Studentstu)實(shí)現(xiàn)輸出一個(gè)學(xué)生的信息。函數(shù)可以定義如下：voidPrintStuInfo(Studentstu){printf("學(xué)號(hào)：%s\n",stu.No);printf("姓名：%s\n",);printf("性別：%c\n",stu.sex);printf("大學(xué)英語(yǔ)成績(jī)：%d\n",stu.english);printf("高等數(shù)學(xué)成績(jī)：%d\n",stu.math);}7.3實(shí)驗(yàn)范例2、算法描述7.3.1范例1

在main()函數(shù)中定義查找表L，然后調(diào)用InitList()函數(shù)對(duì)查找表L進(jìn)行初始化，接著調(diào)用CreateSSTable()函數(shù)將n個(gè)學(xué)生信息存入查找表中，輸入待查找的學(xué)號(hào)存入stdNo字符數(shù)組中，調(diào)用Search_Seq()函數(shù)在L中查找學(xué)號(hào)等于stdNo的學(xué)生，并返回其下標(biāo)。如果返回值不等于0，表示該學(xué)號(hào)的學(xué)生存在，輸出該學(xué)生的所有信息。如果等于0，表示該學(xué)號(hào)的學(xué)生不存在。7.3實(shí)驗(yàn)范例2、算法描述7.3.1范例1#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE100//在main()之前加入類(lèi)型定義和函數(shù)定義intmain(){intm,stdPos;charstdNo[8];SSTableL;InitList(L);printf("---------順序查找---------\n");printf("請(qǐng)輸入順序表的長(zhǎng)度:");scanf("%d",&m);CreateSSTable(L,m);7.3實(shí)驗(yàn)范例2、算法描述7.3.1范例1printf("請(qǐng)輸入需要查找的學(xué)生學(xué)號(hào)：");fflush(stdin);scanf("%s",stdNo);stdPos=Search_Seq(L,stdNo);if(stdPos!=0){printf("存在學(xué)號(hào)為%s的學(xué)生，該學(xué)生信息如下\n",stdNo);PrintStuInfo(L.R[stdPos]);}else{printf("不存在學(xué)號(hào)為%s的學(xué)生！\n",stdNo);}return0;}7.3實(shí)驗(yàn)范例3、算法分析7.3.1范例1

按值查找操作時(shí)間主要耗費(fèi)在比較元素上，而比較的次數(shù)取決于被查元素在表中的位置，平均比較次數(shù)為(n+1)/2，時(shí)間復(fù)雜度為O(n)。通過(guò)設(shè)置監(jiān)視哨，當(dāng)順序表長(zhǎng)度大于1000時(shí)，進(jìn)行一次查找所需的平均時(shí)間比普通算法的時(shí)間幾乎減少一半。7.3實(shí)驗(yàn)范例

二分查找（遞歸算法）：假設(shè)范例1中的順序表已按照學(xué)號(hào)遞增有序，用二分查找方法在該順序表中查找與給定學(xué)號(hào)相等的學(xué)生信息，并輸出該學(xué)生的所有信息。7.3.2范例27.3實(shí)驗(yàn)范例1、問(wèn)題分析7.3.2范例2

能使用二分查找的前提是待查找表是有序的，而且是順序存儲(chǔ)方式。在任務(wù)1所建的查找表基礎(chǔ)上用二分查找查找，在建立查找表時(shí)按學(xué)號(hào)從小到大的順序輸入學(xué)生信息。二分查找是從表的中間元素開(kāi)始查找，如果給定值和中間元素的關(guān)鍵字值相等，則查找成功；如果給定值大于或小于中間元素的關(guān)鍵字值，則在表中大于或小于中間元素的那一半中查找，重復(fù)操作，直到找到或者在某步中查找區(qū)間為空，則查找失敗。7.3實(shí)驗(yàn)范例1、問(wèn)題分析7.3.2范例2

假設(shè)待查找表ST中元素的起止元素下標(biāo)為low和high，查找關(guān)鍵字值為key的元素的步驟為：

（1）判斷l(xiāng)ow是否大于high，是則返回-1，查找結(jié)束；

（2）否則，計(jì)算中間元素的下標(biāo)mid，mid=(low+high)/2，將下標(biāo)為mid的元素的關(guān)鍵字值和key進(jìn)行比較：

如果key和下標(biāo)為mid的元素關(guān)鍵字的值相等，返回mid；

如果key小于下標(biāo)為mid的元素關(guān)鍵字的值，則在下標(biāo)為low和mid-1之間的元素中繼續(xù)查找；

如果key大于下標(biāo)為mid的元素關(guān)鍵字的值，則在下標(biāo)為mid+1和high之間的元素中繼續(xù)查找。7.3實(shí)驗(yàn)范例1、問(wèn)題分析7.3.2范例2

本范例中需要查找和給定學(xué)號(hào)相同的學(xué)生信息，所以key