圖的遍歷和生成樹求解實(shí)現(xiàn)的課程結(jié)構(gòu)設(shè)計(jì).doc

圖的遍歷和生成樹求解實(shí)現(xiàn)的課程結(jié)構(gòu)設(shè)計(jì)一.問題描述： 1.圖的遍歷和生成樹求解實(shí)現(xiàn)圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素（及其孩子結(jié)點(diǎn)）相關(guān)但只能和上一層中一個(gè)元素（即雙親結(jié)點(diǎn)）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。生成樹求解主要利用普利姆和克雷斯特算法求解最小生成樹，只有強(qiáng)連通圖才有生成樹。 2.基本功能1) 先任意創(chuàng)建一個(gè)圖；2) 圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)3) 最小生成樹（兩個(gè)算法）的實(shí)現(xiàn)，求連通分量的實(shí)現(xiàn)4) 要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn) 3.輸入輸出 輸入數(shù)據(jù)類型為整型和字符型，輸出為整型和字符二、 概要設(shè)計(jì)1. 設(shè)計(jì)思路：a.圖的鄰接矩陣存儲(chǔ)：根據(jù)所建無向圖的結(jié)點(diǎn)數(shù)n,建立n*n的矩陣，其中元素全是無窮大（int_max），再將邊的信息存到數(shù)組中。其中無權(quán)圖的邊用1表示，無邊用0表示；有全圖的邊為權(quán)值表示，無邊用表示。b.圖的鄰接表存儲(chǔ)：將信息通過鄰接矩陣轉(zhuǎn)換到鄰接表中，即將鄰接矩陣的每一行都轉(zhuǎn)成鏈表的形式將有邊的結(jié)點(diǎn)進(jìn)行存儲(chǔ)。c.圖的廣度優(yōu)先遍歷：假設(shè)從圖中的某個(gè)頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個(gè)未曾訪問過的鄰接點(diǎn)，然后再訪問此鄰接點(diǎn)的未被訪問的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時(shí)圖中還有未被訪問的，則另選未被訪問的重復(fù)以上步驟，是一個(gè)非遞歸過程。d.圖的深度優(yōu)先遍歷：假設(shè)從圖中某頂點(diǎn)v出發(fā)，依依次訪問v的鄰接頂點(diǎn)，然后再繼續(xù)訪問這個(gè)鄰接點(diǎn)的系一個(gè)鄰接點(diǎn)，如此重復(fù)，直至所有的點(diǎn)都被訪問，這是個(gè)遞歸的過程。e.圖的連通分量：這是對(duì)一個(gè)非強(qiáng)連通圖的遍歷，從多個(gè)結(jié)點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為其連通分量的頂點(diǎn)集。本程序利用的圖的深度優(yōu)先遍歷算法。 2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：ADT Queue數(shù)據(jù)對(duì)象：D=ai| ai ElemSet,i=1,2,3，n,n0數(shù)據(jù)關(guān)系：R1=| ai-1,ai D,i=1,2,3,，n基本操作： InitQueue(&Q) 操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。 QueueEmpty(Q) 初始條件：Q為非空隊(duì)列。 操作結(jié)果：若Q為空隊(duì)列，則返回真，否則為假。 EnQueue(&Q,e) 初始條件：Q為非空隊(duì)列。 操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。 DeQueue(&Q,e) 初始條件：Q為非空隊(duì)列。 操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。ADT QueueADT Graph數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R： R=VR VR=|v,wV且P（v，w）,表示從v到w的弧， 謂詞P（v,w）定義了弧的意義或信息基本操作P： CreatGraph(&G,V,VR); 初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。 操作結(jié)果：按V和VR的定義構(gòu)造圖G。 BFSTraverse(G,visit(); 初始條件：圖G存在，Visit是定點(diǎn)的應(yīng)用函數(shù)。 操作結(jié)果：對(duì)圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過程中對(duì)每個(gè)頂點(diǎn) 調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失 敗，則操作失敗。 DFSTraverse(G,visit(); 初始條件：圖G存在，Visit是定點(diǎn)的應(yīng)用函數(shù)。 操作結(jié)果：對(duì)圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過程中對(duì)每個(gè)頂點(diǎn) 調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失 敗，則操作失敗。 DFStra_fen(G) 初始條件：圖G存在，存在圖的深度優(yōu)先遍歷算法。 操作結(jié)果：從多個(gè)頂點(diǎn)對(duì)圖進(jìn)行深度優(yōu)先遍歷，得到連通分量。ADT Graph;3. 軟件結(jié)構(gòu)設(shè)計(jì)：函數(shù)名返回值類型creatMGraph_L(G)intcreatadj(gra,G)intljjzprint(G)voidadjprint(gra,G)voidBFSTraverse(gra)voidDFStra(gra)intDFSTraverse_fen(gra)intMiniSpanTree_PRIM(g,G.vexnum)intMiniSpanTREE_KRUSCAL(G,gra)void三、 詳細(xì)設(shè)計(jì) 1. 定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu)，及其基本操作的實(shí)現(xiàn)；鄰接矩陣定義:typedef struct ArcCellVRType adj;/VRType是頂點(diǎn)關(guān)系類型。對(duì)無權(quán)圖，用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型InfoType *info;/該弧相關(guān)信息的指針ArcCell,AdjMatrixmaxmax;typedef structVertexType vexsmax;/頂點(diǎn)向量AdjMatrix arcs;/鄰接矩陣int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)MGraph_L;鄰接表的定義:typedef struct ArcNode/弧結(jié)點(diǎn)int adjvex;/該弧指向的頂點(diǎn)的位置struct ArcNode *nextarc;/指向下一條弧的指針I(yè)nfoType *info;/該弧相關(guān)信息的指針ArcNode;typedef struct VNode/鄰接鏈表頂點(diǎn)頭接點(diǎn)VertexType data;/頂點(diǎn)信息ArcNode *firstarc;/指向第一條依附該頂點(diǎn)的弧的指針VNode,AdjList;typedef struct/圖的定義AdjList verticesmax;int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)ALGraph;隊(duì)列定義:typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;/隊(duì)頭指針QueuePtr rear;/隊(duì)尾指針LinkQueue;2 主函數(shù)和其他函數(shù)的偽碼算法；主函數(shù)：int main()int s;char y=y; cout|菜單|endl; cout|-【0、創(chuàng)建一個(gè)無向圖-|endl; cout|-【1、顯示該圖的鄰接矩陣-|endl; cout|-【2、顯示該圖的鄰接表-|endl;cout|-【3、廣度優(yōu)先遍歷-|endl; cout|-【4、深度優(yōu)先遍歷-|endl; cout|-【5、最小生成樹MiniSpanTree_PRIM算法-|endl; cout|-【6、最小生成樹MiniSpanTree_KRUSCAL算法-|endl; cout|-【7、連通分量-|endl;cout|endl;while(y=y)cout請(qǐng)選擇菜單：s;if(s=0)+o;if(o=2)n=0;l=0;o=0;switch(s)case 0:cout創(chuàng)建一個(gè)無向圖：endl;MGraph_L G;creatMGraph_L(G);ALGraph gra;creatadj(gra,G); break;case 1:cout鄰接矩陣顯示如下：endl;ljjzprint(G); break; case 2: cout鄰接表顯示如下：endl; adjprint(gra,G); break; case 3: cout廣度優(yōu)先遍歷：; BFSTraverse(gra); coutendl; break; case 4:cout深度優(yōu)先遍歷：; DFStra(gra); coutendl; break; case 5:if(n=0)cout0)cout若該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)時(shí)，最小生成樹不存在endl;break;elseint i,gmaxmax;for(i=0;i!=G.vexnum;+i)for(int j=0;j!=G.vexnum;+j)gi+1j+1=G.arcsij.adj;cout普利姆算法:endl;MiniSpanTree_PRIM(g,G.vexnum);break; case 6:if(n=0)cout0)cout該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)，最小生成樹不存在endl;break;elsecout克魯斯卡爾算法:endl; MiniSpanTREE_KRUSCAL(G,gra); break; case 7:cout連通分量:endl;DFSTraverse_fen(gra); break;coutendly; if(y=n) break;return 0;鄰接矩陣存儲(chǔ)：int creatMGraph_L(MGraph_L &G)/創(chuàng)建圖用鄰接矩陣表示char v1,v2;int i,j,w;cout請(qǐng)輸入頂點(diǎn)和弧的個(gè)數(shù)G.vexnumG.arcnum;cout輸入各個(gè)頂點(diǎn)endl;for(i=0;iG.vexsi;for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj=int_max;G.=NULL;for(int k=0;kG.arcnum;+k)cout輸入一條邊依附的頂點(diǎn)和權(quán)v1v2w;/輸入一條邊依附的兩點(diǎn)及權(quán)值i=localvex(G,v1);/確定頂點(diǎn)V1和V2在圖中的位置j=localvex(G,v2);G.arcsij.adj=w;G.arcsji.adj=w;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj!=1&G.arcsij.adj=1)cout這是一個(gè)有權(quán)圖endl;else cout這是一個(gè)無權(quán)圖endl;cout圖G鄰接矩陣創(chuàng)建成功！endl;return G.vexnum;鄰接矩陣的輸出：void ljjzprint(MGraph_L G) /鄰接矩陣的輸出int i,j;if(n=0)for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj=int_max)cout0 ;else coutG.arcsij.adj ;coutendl;elsefor(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj=int_max)cout ;else coutG.arcsij.adj ;coutadjvex=j;arc-nextarc=gra.verticesi.firstarc;gra.verticesi.firstarc=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout圖G鄰接表創(chuàng)建成功！endl;return 1;鄰接表輸出：void adjprint(ALGraph gra,MGraph_L G) /鄰接表輸出int i;for(i=0;i!=gra.vexnum;+i)ArcNode *p;couti,G.vexsi;p=gra.verticesi.firstarc;while(p!=NULL)coutadjvexnextarc;coutEnd;coutnext=NULL;return 1;入隊(duì)：Status EnQueue(LinkQueue &Q,QElemType e)/入隊(duì),插入元素e為Q的新的隊(duì)尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)return 0;/存儲(chǔ)分配失敗p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return 1;出隊(duì)：Status DeQueue(LinkQueue &Q,QElemType &e)/出隊(duì)，若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回，并返回真，否則假Q(mào)ueuePtr p;if(Q.front=Q.rear)return 0;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return 1;判斷隊(duì)為空：Status QueueEmpty(LinkQueue Q)/判斷隊(duì)為空if(Q.front=Q.rear) return 1;return 0;廣度優(yōu)先遍歷：void BFSTraverse(ALGraph gra)int i,e;LinkQueue q;for(i=0;i!=gra.vexnum;+i)visitedi=0;InitQueue(q);for(i=0;i!=gra.vexnum;+i)if(!visitedi) visitedi=1;cout=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;coutgra.verticeswe.data;EnQueue(q,we);深度優(yōu)先遍歷：int DFS(ALGraph gra,int i)visitedi=1;int we1;cout=0;we=nextadjvex(gra,gra.verticesi,we)we1=we;if(visitedwe=0)DFS(gra,we);we=we1;return 1;int DFStra(ALGraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);return 0;連通分量：int DFSTraverse_fen(ALGraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);cout0為有權(quán)圖，此時(shí)輸出的時(shí)候用代替10000；n=0為無權(quán)圖，此時(shí)輸出的時(shí)候用0代替10000. b.程序中有的功能對(duì)某些圖是不適用的，比如無權(quán)圖沒有最小生成樹，非強(qiáng)連通圖沒有最小生成樹等。所以在程序中又新增了全局變量l,l0時(shí)表示為非強(qiáng)連通圖，則在求最小生成樹時(shí)報(bào)錯(cuò)。 C.當(dāng)程序先創(chuàng)建一個(gè)有權(quán)圖后，n的值會(huì)大于1，第二次創(chuàng)無權(quán)圖時(shí)也會(huì)被程序認(rèn)為有權(quán)圖，所以在程序中在定義全局變量o（初值為0）,來判斷創(chuàng)建了幾次圖，當(dāng)?shù)诙蝿?chuàng)建圖，即o=2時(shí)，所有全局變量在開始全歸零。4. 程序中可以改進(jìn)的地方說明；當(dāng)建立一個(gè)圖時(shí)先得求其連通分量，從而確定全局變量l的值，從而才能判斷該圖是否有最小生成樹。5、 測(cè)試結(jié)果創(chuàng)建一個(gè)無權(quán)圖：創(chuàng)建一個(gè)費(fèi)強(qiáng)連通的有權(quán)圖：創(chuàng)建一個(gè)有權(quán)連通圖：6、 用戶手冊(cè)a.先選0創(chuàng)建一個(gè)圖。b.選擇y繼續(xù)操作。c.按照菜單編碼選擇操作。七、體會(huì)與自我評(píng)價(jià) 在做這個(gè)程序的時(shí)候你首先必須知道圖的一些概念，圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素（及其孩子結(jié)點(diǎn)）相關(guān)但只能和上一層中一個(gè)元素（即雙親結(jié)點(diǎn)）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。當(dāng)我們拿到一個(gè)圖時(shí)，我們對(duì)該圖的遍歷就要有一些方法，所以有了深度優(yōu)先遍歷和廣度優(yōu)先遍歷，我們要明白這兩種遍歷是怎么實(shí)現(xiàn)的，然后根據(jù)我們?nèi)四X中的方法把它寫成電腦算法。對(duì)一個(gè)圖我們還定義了連通分量，所以將圖存到電腦中時(shí)，我們對(duì)連通分量得有個(gè)算法。求圖的最小生成樹有兩種算法，普利姆是從結(jié)點(diǎn)出發(fā)尋找權(quán)最小的邊，知道所有結(jié)點(diǎn)都練通了；而克魯斯卡爾算法則是從邊出發(fā)，尋找使圖連通的權(quán)值最小邊的方法。算法的實(shí)現(xiàn)從人腦到電腦的轉(zhuǎn)變是比較復(fù)雜的一件事，要求做到具體到實(shí)現(xiàn)該方法的每一個(gè)步驟，然后再將每一個(gè)步驟通過代碼實(shí)現(xiàn)。這要求我們要明確各個(gè)數(shù)據(jù)元素和個(gè)元素之間的關(guān)系，然后才能明確使用算法去調(diào)用這些數(shù)據(jù)。通過本次的課程設(shè)計(jì)，我對(duì)數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)識(shí)，明白了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)，數(shù)據(jù)關(guān)系，及對(duì)其操作的方法。但同時(shí)也發(fā)現(xiàn)在自己有很多的不足，在使用語言和如何精煉語言需要進(jìn)行更多的訓(xùn)練。 源代碼：#include #include using namespace std;#define int_max 10000/最大值static int n=0;/全局變量，判斷有權(quán)圖和無權(quán)圖static int o=0;/全局變量，清除BUGstatic int l=0;/全局變量，清除BUG#define inf 9999/最小值的最大值#define max 20/最大頂點(diǎn)個(gè)數(shù)typedef int VRType,QElemType,Status;typedef char InfoType,VertexType; /|鄰接矩陣|/-鄰接矩陣定義-typedef struct ArcCellVRType adj;/VRType是頂點(diǎn)關(guān)系類型。對(duì)無權(quán)圖，用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型InfoType *info;/該弧相關(guān)信息的指針ArcCell,AdjMatrixmaxmax;typedef structVertexType vexsmax;/頂點(diǎn)向量AdjMatrix arcs;/鄰接矩陣int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)MGraph_L;/-int localvex(MGraph_L G,char v)/返回V的位置int i=0;while(G.vexsi!=v)+i;return i;int creatMGraph_L(MGraph_L &G)/創(chuàng)建圖用鄰接矩陣表示char v1,v2;int i,j,w;cout請(qǐng)輸入頂點(diǎn)和弧的個(gè)數(shù)G.vexnumG.arcnum;cout輸入各個(gè)頂點(diǎn)endl;for(i=0;iG.vexsi;for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj=int_max;G.=NULL;for(int k=0;kG.arcnum;+k)cout輸入一條邊依附的頂點(diǎn)和權(quán)v1v2w;/輸入一條邊依附的兩點(diǎn)及權(quán)值i=localvex(G,v1);/確定頂點(diǎn)V1和V2在圖中的位置j=localvex(G,v2);G.arcsij.adj=w;G.arcsji.adj=w;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj!=1&G.arcsij.adj=1)cout這是一個(gè)有權(quán)圖endl;else cout這是一個(gè)無權(quán)圖endl;cout圖G鄰接矩陣創(chuàng)建成功！endl;return G.vexnum;void ljjzprint(MGraph_L G) /鄰接矩陣的輸出int i,j;if(n=0)for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj=int_max)cout0 ;else coutG.arcsij.adj ;coutendl;elsefor(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj=int_max)cout ;else coutG.arcsij.adj ;coutadjvex=j;arc-nextarc=gra.verticesi.firstarc;gra.verticesi.firstarc=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout圖G鄰接表創(chuàng)建成功！endl;return 1;void adjprint(ALGraph gra,MGraph_L G) /鄰接表輸出int i;for(i=0;i!=gra.vexnum;+i)ArcNode *p;couti,G.vexsi;p=gra.verticesi.firstarc;while(p!=NULL)coutadjvexnextarc;coutEnd;coutnext=NULL;return 1;Status EnQueue(LinkQueue &Q,QElemType e)/入隊(duì),插入元素e為Q的新的隊(duì)尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)return 0;/存儲(chǔ)分配失敗p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return 1;Status DeQueue(LinkQueue &Q,QElemType &e)/出隊(duì)，若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回，并返回真，否則假Q(mào)ueuePtr p;if(Q.front=Q.rear)return 0;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return 1;Status QueueEmpty(LinkQueue Q)/判斷隊(duì)為空if(Q.front=Q.rear) return 1;return 0;/-圖的遍歷-int visitedmax;/訪問標(biāo)記int we;int firstadjvex(ALGraph gra,VNode v)/返回依附頂點(diǎn)V的第一個(gè)點(diǎn) /即以V為尾的第一個(gè)結(jié)點(diǎn)if(v.firstarc!=NULL)return v.firstarc-adjvex;int nextadjvex(ALGraph gra,VNode v,int w)/返回依附頂點(diǎn)V的相對(duì)于W的下一個(gè)頂點(diǎn)ArcNode *p;p=v.firstarc;while(p!=NULL&p-adjvex!=w)p=p-nextarc;if(p-adjvex=w&p-nextarc!=NULL)p=p-nextarc;return p-adjvex;if(p-adjvex=w&p-nextarc=NULL)return -10;/-廣度優(yōu)先遍歷-void BFSTraverse(ALGraph gra)int i,e;LinkQueue q;for(i=0;i!=gra.vexnum;+i)visitedi=0;InitQueue(q);for(i=0;i!=gra.vexnum;+i)if(!visitedi) visitedi=1;cout=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;coutgra.verticeswe.data;EnQueue(q,we);/-深度優(yōu)先遍歷-int DFS(ALGraph gra,int i)visitedi=1;int we1;cout=0;we=nextadjvex(gra,gra.verticesi,we)we1=we;if(visitedwe=0)DFS(gra,we);we=we1;return 1;int DFStra(ALGraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);return 0;/-求連通分量-int DFSTraverse_fen(ALGraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);coutendl;l+;return 0;/-最小生成樹的普利姆算法-typedef structint adjvex;int lowcost;closedge;int MiniSpanTree_PRIM(int gmax,int n) int lowcostmax,prevexmax; /lowcost存儲(chǔ)