【正文】 的值:1 2 3 4 5 6 7 8↙輸入圖中10條邊(弧)的信息u v:1 3 1 2 2 5 2 4 3 7 3 6 8 7 8 6 8 5 8 4↙有向圖G1的鄰接表為:0 (1): [1] [3]1 (2):2 (3): [1] [4]3 (4): [1] [4]4 (5): [0] [1]5 (6): [2] [4]有向圖G1的深度優(yōu)先遍歷序列為:1 2 4 5 3 6無向圖G2的鄰接表為:0 (1): [1] [2]1 (2): [3] [4] [0]2 (3): [5] [6] [0]3 (4): [7] [1]4 (5): [7] [1]5 (6): [7] [2]6 (7): [7] [2]7 (8): [3] [4] [5] [6]無向圖G2的深度優(yōu)先遍歷序列為:1 2 4 8 5 6 3 7說明：（1），并以鄰接表中第一個(gè)頂點(diǎn)開始分別對(duì)其進(jìn)行深度優(yōu)先遍歷，并顯示輸出遍歷序列。（2）對(duì)同一個(gè)圖，如果輸入的頂點(diǎn)值序列的順序不同或輸入的邊（或弧）的順序不同，那么創(chuàng)建的鄰接表也不同，從而得到的深度優(yōu)先遍歷序列也不同。（3）圖的深度優(yōu)先遍歷的時(shí)間復(fù)雜度取決于圖的存儲(chǔ)結(jié)構(gòu)。當(dāng)以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)的時(shí)間復(fù)雜度為O(n2)，當(dāng)以鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)的時(shí)間復(fù)雜度為O(e+n)。1．廣度優(yōu)先遍歷的定義圖的廣度優(yōu)先搜索類似于樹的層次遍歷，也是圖的一種普遍采用的遍歷算法。設(shè)初始狀態(tài)是圖中的所有頂點(diǎn)均未被訪問。廣度優(yōu)先遍歷過程如下：首先訪問指定的起始頂點(diǎn)u，再按某種順序依次訪問u的所有未被訪問過的鄰接點(diǎn)序列：v1,v2,v3,…,vk；然后按照次序v1,v2,v3,…,vk逐個(gè)訪問其中每個(gè)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)（按某種順序），繼續(xù)以上過程，直到圖中所有和初始頂點(diǎn)u有路徑相通的頂點(diǎn)均被訪問過為止。如果圖中還存在與初始頂點(diǎn)u不連通的頂點(diǎn)，則任選一個(gè)沒被訪問過的頂點(diǎn)做起點(diǎn)，重復(fù)上述過程，直到圖中所有的頂點(diǎn)均被訪問過為止。說明：根據(jù)廣度優(yōu)先搜索的定義可知，同一個(gè)圖，從同一個(gè)頂點(diǎn)開始，可以得到多種不同的廣度優(yōu)先遍歷序列。所以，圖的廣度優(yōu)先遍歷序列不唯一。例如：(1) ，從頂點(diǎn)1開始的廣度優(yōu)先遍歷序列有以下6種：1) 3； 2) 4； 3) 3；4) 2； 5) 2； 6) 4。(2) ，從頂點(diǎn)v1開始的廣度優(yōu)先遍歷序列有以下2種：1) v1，v2，v3，v4； 2) v1，v3，v2，v4。(3) ，從頂點(diǎn)1開始，按頂點(diǎn)編號(hào)遞增順序進(jìn)行廣度優(yōu)先遍歷的序列為：8。從頂點(diǎn)1開始，按頂點(diǎn)編號(hào)遞減順序進(jìn)行廣度優(yōu)先遍歷的序列為：8。2．廣度優(yōu)先遍歷的算法實(shí)現(xiàn)和深度優(yōu)先算法類似，[v].flag，另外還需要一個(gè)隊(duì)列Q來存放已被訪問的頂點(diǎn)的標(biāo)號(hào)。在圖的某個(gè)連通分量中，當(dāng)訪問了一個(gè)頂點(diǎn)后，該頂點(diǎn)的標(biāo)號(hào)入隊(duì)；然后，從隊(duì)列頭部取出一個(gè)頂點(diǎn)下標(biāo)，依次訪問該下標(biāo)所對(duì)應(yīng)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)，并依次將各個(gè)訪問過的鄰接點(diǎn)的下標(biāo)入隊(duì)，直到隊(duì)列為空為止。(1)遍歷算法實(shí)現(xiàn)函數(shù)void BFSTraverse_ALG(ALGraph G)實(shí)現(xiàn)對(duì)鄰接表表示的圖G的廣度優(yōu)先遍歷。void BFSTraverse_ALG(ALGraph G){ int v,w,u,n=。 int* Q=new int[]。 //定義頂點(diǎn)標(biāo)號(hào)隊(duì)列Q int front=0,real=0。 ArcNode* pr。 for(v=0。v。v++) { if(![v].flag) { [v].flag=1。 //修改標(biāo)志 cout[v].data39。 39。 //訪問該結(jié)點(diǎn) Q[real++]=v。 //頂點(diǎn)標(biāo)號(hào)入隊(duì) real%=n。 while(front!=real) //當(dāng)隊(duì)列Q不空 { w=Q[front++]。 front%=n。 //頂點(diǎn)標(biāo)號(hào)出隊(duì) pr=[w].nextarc。 while(pr) { u=pradjvex。 if(![u].flag) { [u].flag=1。 //修改標(biāo)志 cout[u].data39。 39。 //訪問該結(jié)點(diǎn) Q[real++]=u。 real%=n。 //頂點(diǎn)標(biāo)號(hào)入隊(duì) } pr=prnextarc。 //進(jìn)入下一個(gè)鄰接點(diǎn) }//end while }//end while }//end if }//end for coutendl。}(2)主函數(shù)調(diào)用演示程序主函數(shù)首先建立有向圖G1和無向圖G2的鄰接表，再分別對(duì)其進(jìn)行廣度優(yōu)先遍歷并顯示輸出鄰接表和遍歷序列。void main(){ ALGraph G1,G2。 GKind gk1=DG,gk2=UDG。 cout建立一個(gè)有向圖的鄰接表G1:\n。 CreateGraph_AL(G1,gk1)。 cout建立一個(gè)無向圖的鄰接表G2:\n。 CreateGraph_AL(G2,gk2)。 cout有向圖G1的鄰接表為:\n。 DisplyAL(G1)。 cout有向圖G1的廣度優(yōu)先遍歷序列為:\n。 BFSTraverse_ALG(G1)。 cout無向圖G2的鄰接表為:\n。 DisplyAL(G2)。 cout無向圖G2的廣度優(yōu)先遍歷序列為:\n。 BFSTraverse_ALG(G2)。}程序運(yùn)行演示結(jié)果如下：建立一個(gè)有向圖的鄰接表G1:輸入頂點(diǎn)數(shù)和邊(弧)數(shù)vexnum arum:6 10↙按某種順序輸入6個(gè)頂點(diǎn)的值:1 2 3 4 5 6↙輸入圖中10條邊(弧)的信息u v:1 4 1 2 3 5 3 2 4 5 4 2 5 2 5 1 6 5 6 3↙建立一個(gè)無向圖的鄰接表G2:輸入頂點(diǎn)數(shù)和邊(弧)數(shù)vexnum arum:8 10↙按某種順序輸入8個(gè)頂點(diǎn)的值:1 2 3 4 5 6 7 8↙輸入圖中10條邊(弧)的信息u v:1 3 1 2 2 5 2 4 3 7 3 6 8 7 8 6 8 5 8 4↙有向圖G1的鄰接表為:0 (1): [1] [3]1 (2):2 (3): [1] [4]3 (4): [1] [4]4 (5): [0] [1]5 (6): [2] [4]有向圖G1的廣度優(yōu)先遍歷序列為:1 2 4 5 3 6無向圖G2的鄰接表為:0 (1): [1] [2]1 (2): [3] [4] [0]2 (3): [5] [6] [0]3 (4): [7] [1]4 (5): [7] [1]5 (6): [7] [2]6 (7): [7] [2]7 (8): [3] [4] [5] [6]無向圖G2的廣度優(yōu)先遍歷序列為:1 2 3 4 5 6 7 8說明：（1）：GG2。并分別對(duì)其進(jìn)行廣度優(yōu)先遍歷，顯示輸出遍歷序列。廣度優(yōu)先算法的時(shí)間復(fù)雜度與深度優(yōu)先算法相同。（2）程序以鄰接表中第一個(gè)頂點(diǎn)開始對(duì)圖進(jìn)行廣度優(yōu)先遍歷。如果輸入的頂點(diǎn)值序列的順序不同或輸入的邊（或弧）的順序不同，那么得到的廣度優(yōu)先遍歷序列也不同。（代價(jià)）生成樹利用圖的遍歷算法可以求解圖的連通性問題，進(jìn)而可以求得無向圖的生成樹或生成森林。1．生成樹的概念設(shè)G=(V,E)是一個(gè)連通的無向圖，則從圖G中的任一頂點(diǎn)出發(fā)，可以訪問到G的全部頂點(diǎn)。在對(duì)G的遍歷過程中，所經(jīng)過的邊集設(shè)為T(G)，沒有經(jīng)過的邊集設(shè)為B(G)，顯然有T∪B=E，且T∩B=216。對(duì)于圖G1=(V,T)，由于V(G1)=V(G)，E(G1)E(G)，所以G1是G的一個(gè)連通子圖，且G1中含有G的所有頂點(diǎn)。我們把連通圖中的所有頂點(diǎn)加上遍歷時(shí)經(jīng)過的所有邊所構(gòu)成的子圖稱為生成樹。顯然G1是G的生成樹。說明：(1) 由于具有n個(gè)頂點(diǎn)的連通圖G中至少有n1條邊，而G的生成樹中恰好有n1條邊，所以生成樹是連通圖的一個(gè)極小連通子圖。(2) 若在生成樹中任意加上一條邊，則必然形成回路。(3) 一個(gè)連通圖的生成樹不是唯一的，這是由于遍歷圖時(shí)選擇的起點(diǎn)不同、遍歷的算法不同（深度優(yōu)先或廣度優(yōu)先）、結(jié)點(diǎn)排列次序不同，因而會(huì)產(chǎn)生不同的生成樹。例如，(a)的4種不同的生成樹(b)。(4) 對(duì)于不連通的無向圖，從任意頂點(diǎn)出發(fā)，不能訪問到圖的所有頂點(diǎn)，只能得到連通分量的生成樹。一個(gè)圖的所有連通分量的生成樹組成該圖的生成森林。2．生成樹的算法實(shí)現(xiàn)對(duì)于連通的無向圖，由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。下面給出深度優(yōu)先生成樹（或森林）的算法實(shí)現(xiàn)過程。(1)二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)為了用樹的孩子兄弟表示法來表示生成樹（或森林），下面給出其二叉鏈表的結(jié)構(gòu)定義。typedef struct CSNode{ VType data。 CSNode *firstchild,*nextsibling。}*CSTree。(2)生成樹的算法實(shí)現(xiàn)函數(shù)void DFSTree(ALGraph amp。G,int v,CSTreeamp。 T)的功能是，從結(jié)點(diǎn)v開始對(duì)無向連通圖G進(jìn)行深度優(yōu)先遍歷得到深度優(yōu)先生成樹T。void DFSTree(ALGraph amp。G,int v,CSTreeamp。 T){ ArcNode* p。 CSTree q,s=T。 int w,first=1。 [v].flag=1。 for(p=[v].nextarc。p。p=pnextarc) { w=padjvex。 if(![w].flag) { q=new CSNode。 //動(dòng)態(tài)分配結(jié)點(diǎn)q qdata=[w].data。 //為結(jié)點(diǎn)q賦值 qfirstchild=qnextsibling=NULL。 if(first){ first=0。 Tfirstchild=q。 } //w是第一個(gè)v的未被訪問的鄰接點(diǎn) else{ snextsibling=q。 s=q。 } //w是v的其它未被訪問的鄰接點(diǎn) DFSTree(G,w,q)。 //從w出發(fā)深度優(yōu)先遍歷G，建立子生成樹q }//end_if }//end_for}(3)生成森林的算法實(shí)現(xiàn)函數(shù)void DFSForest(ALGraph G,CSTreeamp。 T)的功能是，從無向圖G的第一個(gè)結(jié)點(diǎn)（按鄰接表中的結(jié)點(diǎn)順序）開始，對(duì)G進(jìn)行深度優(yōu)先遍歷得到深度優(yōu)先生成森林（或樹）T。void DFSForest(ALGraph G,CSTreeamp。 T){ CSTree p,q。 int v。 T=NULL。 for(v=0。v。v++)[v].flag=0。 //初始化結(jié)點(diǎn)訪問標(biāo)志 for(v=0。v。v++) if([v].flag==0) { p=new CSNode。 //動(dòng)態(tài)分配結(jié)點(diǎn)p pdata=[v].data。 //為結(jié)點(diǎn)p賦值 pfirstchild=pnextsibling=NULL。 if(!T)T=q=p。 //v是第一棵生成樹的根 else{ qnextsibling=p。 q=p。} //v是其它生成樹的根 DFSTree(G,v,p)。 //建立以p為根的生成樹 }}顯然，該算法的時(shí)間復(fù)雜度與深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度相同。（代價(jià)）生成樹1．最小生成樹的概念對(duì)于無向網(wǎng)，因?yàn)樗倪吺菐в袡?quán)值的，而一個(gè)圖的生成樹是不唯一的，那么，就產(chǎn)生了這樣一個(gè)問題：如何找到一個(gè)各邊的權(quán)值總和最小的生成樹，這種生成樹稱為最?。ù鷥r(jià)）生成樹。最小生成樹問題在實(shí)際應(yīng)用中很有意義，比如，要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，最多有n(n1)/2條路線，而連通這n個(gè)城市僅需要其中的n1條路線（圖的生成樹）即可，由于每對(duì)城市之間的距離不一樣，鋪設(shè)線路所花費(fèi)的經(jīng)濟(jì)價(jià)格也不一同，此時(shí)，自然會(huì)考慮到如何在最節(jié)省經(jīng)費(fèi)（最小代價(jià)）的前提下建立通信網(wǎng)。例如，(b)(a)的最小生成樹。常用的最小代價(jià)生成樹算法有兩種，即普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法。這兩種算法都用了最小生成樹的MST性質(zhì)，即：設(shè)N=(V,VR)是一個(gè)連通網(wǎng)，U