【正文】 這兩種算法都用了最小生成樹的MST性質(zhì)，即：設(shè)N=(V,VR)是一個連通網(wǎng)，U是頂點。例如，(b)(a)的最小生成樹。（代價）生成樹1．最小生成樹的概念對于無向網(wǎng)，因為它的邊是帶有權(quán)值的，而一個圖的生成樹是不唯一的，那么，就產(chǎn)生了這樣一個問題：如何找到一個各邊的權(quán)值總和最小的生成樹，這種生成樹稱為最小（代價）生成樹。} //v是其它生成樹的根 DFSTree(G,v,p)。 //v是第一棵生成樹的根 else{ qnextsibling=p。 //為結(jié)點p賦值 pfirstchild=pnextsibling=NULL。v++) if([v].flag==0) { p=new CSNode。 //初始化結(jié)點訪問標(biāo)志 for(v=0。v。 T=NULL。 T){ CSTree p,q。 T)的功能是，從無向圖G的第一個結(jié)點（按鄰接表中的結(jié)點順序）開始，對G進(jìn)行深度優(yōu)先遍歷得到深度優(yōu)先生成森林（或樹）T。 } //w是v的其它未被訪問的鄰接點 DFSTree(G,w,q)。 } //w是第一個v的未被訪問的鄰接點 else{ snextsibling=q。 if(first){ first=0。 //動態(tài)分配結(jié)點q qdata=[w].data。p=pnextarc) { w=padjvex。 for(p=[v].nextarc。 int w,first=1。 T){ ArcNode* p。void DFSTree(ALGraph amp。G,int v,CSTreeamp。}*CSTree。typedef struct CSNode{ VType data。下面給出深度優(yōu)先生成樹（或森林）的算法實現(xiàn)過程。一個圖的所有連通分量的生成樹組成該圖的生成森林。例如，(a)的4種不同的生成樹(b)。(2) 若在生成樹中任意加上一條邊，則必然形成回路。顯然G1是G的生成樹。對于圖G1=(V,T)，由于V(G1)=V(G)，E(G1)E(G)，所以G1是G的一個連通子圖，且G1中含有G的所有頂點。1．生成樹的概念設(shè)G=(V,E)是一個連通的無向圖，則從圖G中的任一頂點出發(fā)，可以訪問到G的全部頂點。如果輸入的頂點值序列的順序不同或輸入的邊（或弧）的順序不同，那么得到的廣度優(yōu)先遍歷序列也不同。廣度優(yōu)先算法的時間復(fù)雜度與深度優(yōu)先算法相同。}程序運行演示結(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。 cout無向圖G2的廣度優(yōu)先遍歷序列為:\n。 cout無向圖G2的鄰接表為:\n。 cout有向圖G1的廣度優(yōu)先遍歷序列為:\n。 cout有向圖G1的鄰接表為:\n。 cout建立一個無向圖的鄰接表G2:\n。 cout建立一個有向圖的鄰接表G1:\n。void main(){ ALGraph G1,G2。 //進(jìn)入下一個鄰接點 }//end while }//end while }//end if }//end for coutendl。 real%=n。 39。 if(![u].flag) { [u].flag=1。 //頂點標(biāo)號出隊 pr=[w].nextarc。 while(front!=real) //當(dāng)隊列Q不空 { w=Q[front++]。 //訪問該結(jié)點 Q[real++]=v。 //修改標(biāo)志 cout[v].data39。v。 ArcNode* pr。 int* Q=new int[]。(1)遍歷算法實現(xiàn)函數(shù)void BFSTraverse_ALG(ALGraph G)實現(xiàn)對鄰接表表示的圖G的廣度優(yōu)先遍歷。2．廣度優(yōu)先遍歷的算法實現(xiàn)和深度優(yōu)先算法類似，[v].flag，另外還需要一個隊列Q來存放已被訪問的頂點的標(biāo)號。(3) ，從頂點1開始，按頂點編號遞增順序進(jìn)行廣度優(yōu)先遍歷的序列為：8。例如：(1) ，從頂點1開始的廣度優(yōu)先遍歷序列有以下6種：1) 3； 2) 4； 3) 3；4) 2； 5) 2； 6) 4。說明：根據(jù)廣度優(yōu)先搜索的定義可知，同一個圖，從同一個頂點開始，可以得到多種不同的廣度優(yōu)先遍歷序列。廣度優(yōu)先遍歷過程如下：首先訪問指定的起始頂點u，再按某種順序依次訪問u的所有未被訪問過的鄰接點序列：v1,v2,v3,…,vk；然后按照次序v1,v2,v3,…,vk逐個訪問其中每個頂點的所有未被訪問過的鄰接點（按某種順序），繼續(xù)以上過程，直到圖中所有和初始頂點u有路徑相通的頂點均被訪問過為止。1．廣度優(yōu)先遍歷的定義圖的廣度優(yōu)先搜索類似于樹的層次遍歷，也是圖的一種普遍采用的遍歷算法。（3）圖的深度優(yōu)先遍歷的時間復(fù)雜度取決于圖的存儲結(jié)構(gòu)。}程序運行演示結(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 4 8 5 6 3 7說明：（1），并以鄰接表中第一個頂點開始分別對其進(jìn)行深度優(yōu)先遍歷，并顯示輸出遍歷序列。 cout無向圖G2的深度優(yōu)先遍歷序列為:\n。 cout無向圖G2的鄰接表為:\n。 cout有向圖G1的深度優(yōu)先遍歷序列為:\n。 cout有向圖G1的鄰接表為:\n。 cout建立一個無向圖的鄰接表G2:\n。 cout建立一個有向圖的鄰接表G1:\n。void main(){ ALGraph G1,G2。 coutendl。v。void DFSTraverse_ALG(ALGraph G){ int v。 if(![w].flag)DFS_ALG(G,w)。p。 //訪問該結(jié)點 [v].flag=1。 cout[v].data39。G,int v){ int w。G,int v)的功能是，對以鄰接表方式存儲的圖G，從頂點編號為v的頂點開始，用遞歸的方式，深度優(yōu)先遍歷該頂點所在的連通分量。2．深度優(yōu)先遍歷的算法實現(xiàn)深度優(yōu)先算法，[v].flag，頂點一旦被訪問則其相應(yīng)的標(biāo)志由0修改為1。(4) ，從頂點1開始，按頂點編號遞增順序進(jìn)行深度優(yōu)先遍歷的序列為：7。(2) (b)所示的無向圖，從頂點v1開始的深度優(yōu)先遍歷序列有以下5種：1) v1，v2，v5，v3，v4；2) v1，v2，v5，v4，v3；3) v1，v3，v4，v5，v2；4) v1，v3，v5，v2，v4；5) v1，v3，v5，v4，v2。所以，圖的深度優(yōu)先遍歷序列不唯一。若它還有鄰接的頂點未被訪問過，則從這些未被訪問過的頂點中任意選取一個頂點，重復(fù)上述過程，直到所有的頂點都被訪問過為止。深度優(yōu)先遍歷過程為：首先訪問指定的起始頂點u，然后選取與u鄰接的未被訪問的任一頂點v訪問之，再選取與v鄰接的未被訪問的任一頂點w訪問之。1．深度優(yōu)先遍歷的定義圖的深度優(yōu)先搜索類似于樹的先根遍歷，是樹的先根遍歷的推廣。為了方便起見，我們在圖的鄰接矩陣和鄰接表存儲的頂點序列vexs[]（鄰接矩陣）和vertices[]（鄰接表）中均增設(shè)了用于表示該頂點是否被訪問過的標(biāo)志域flag。為了保證在遍歷過程中每個頂點僅被訪問一次，必須記下已訪問過的頂點。圖的遍歷算法是圖的諸多應(yīng)用中的基礎(chǔ)，例如求解圖的連通性、生成樹、拓?fù)渑判颉㈥P(guān)鍵路徑等問題中都是以圖的遍歷算法為基礎(chǔ)。（2）從存儲結(jié)構(gòu)可以看出，在鄰接多重結(jié)構(gòu)存儲的鏈表中很容易算出一個頂點的度，并且建立鄰接多重鏈表的時間復(fù)雜度與建立鄰接表的時間復(fù)雜度相同，所以在無向圖（或網(wǎng)）的應(yīng)用中，常常用鄰接多重鏈表作為存儲結(jié)構(gòu)。 DisplyAMLG(G2)。 DisplyAMLG(G1)。 CreateGraph_AMLG(G2,gk2)。 CreateGraph_AMLG(G1,gk1)。 GKind gk1=DG,gk2=DN。 }//end for} (5)程序演示主程序代碼程序中分別建立一個無向圖(G1)和一個無向網(wǎng)(G2)的鄰接多重鏈表，并按鄰接表的形式顯示所建立的的鄰接多重鏈表的內(nèi)容。 //指針指向下一個邊結(jié)點 else p=pjlink。 cout] 。 39。pivex。pjvex39。 else cout39。 39。[39。 couti ([i].data): 。i。 cout按鄰接表顯示結(jié)果為：\n。void DisplyAMLG(AMLGraph G){ int i。 [j].firsedge=pr。 //將輸入的邊插入到相應(yīng)鏈表的首部 [i].firsedge=pr。 //j從位置值轉(zhuǎn)換為下標(biāo)值 if(==DN)cinprinfo。 //動態(tài)分配邊的存儲空間 privex=i。(j=LocateVex_AMLG(G,v))))。 } while(!((i=LocateVex_AMLG(G,u))amp。k。 else cout輸入圖中條邊和權(quán)的信息u v w:\n。 //輸入所有頂點的信息到data中 [i].firsedge=NULL。i。 //為頂點數(shù)組分配內(nèi)存空間 cout按某種順序輸入個頂點的值:\n。 cin。 =kind。 VType u,v。void CreateGraph_AMLG(AMLGraphamp。}(3)建立鄰接多重鏈表的算法實現(xiàn)函數(shù)void CreateGraph_AMLG(AMLGraphamp。 if(i)return(i+1)。i。int LocateVex_AMLG(AMLGraph G,VType u) { int i。}。 //鏈表頭結(jié)點數(shù)組指針 int vexnum,edgenum。