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