圖遍歷的演示實(shí)習(xí)報(bào)告

圖遍歷的演示題目:諸多波及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試設(shè)計(jì)一種程序,演示在連通和非連通的無(wú)向圖上訪問(wèn)所有結(jié)點(diǎn)的操作一、需求分析1、以鄰接多重表為存儲(chǔ)構(gòu)造；2、實(shí)現(xiàn)連通和非連通的無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷；3、以顧客指定的結(jié)點(diǎn)為起點(diǎn),分別輸出每種遍歷下的結(jié)點(diǎn)訪問(wèn)序列和生成樹的邊集；二、概要設(shè)計(jì)1、設(shè)定圖的抽象數(shù)據(jù)類型:ADTGraph{數(shù)據(jù)對(duì)象V:V是具有相似特性的數(shù)據(jù)元素的集合,稱為點(diǎn)集.數(shù)據(jù)關(guān)系R:R={VR}VR={(v,w)|v,w屬于V,(v,w)表達(dá)v和w之間存在的途徑}基本操作P:CreatGraph(&G,V,VR)初始條件:V是圖的頂點(diǎn)集,VR是圖中弧的集合.操作成果:按V和VR是定義構(gòu)造圖G.DestroyGraph(&G)初始條件:圖G存在操作成果:銷毀圖GLocateVex(G,u)初始條件:圖G存在,u和G中頂點(diǎn)有相似的特性操作成果:若圖G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中的位置;否則返回其他信息GetVex(G,v)初始條件:圖G存在,v是G中頂點(diǎn)操作成果:返回v的值FirstAjvex(G,v)初始條件:圖G存在,v是G中頂點(diǎn)操作成果:返回v的第一種鄰接頂點(diǎn),若頂在圖中沒(méi)有鄰接頂點(diǎn),則返回為空NextAjvex(G,v,w)初始條件:圖G存在,v是G中頂點(diǎn),w是v的鄰接頂點(diǎn)操作成果:返回v的下一種鄰接頂點(diǎn),若w是v的最終一種鄰接頂點(diǎn),則返回空DeleteVexx(&G,v)初始條件:圖G存在,v是G中頂點(diǎn)操作成果:刪除頂點(diǎn)v已經(jīng)其有關(guān)的弧DFSTraverse(G,visit())初始條件:圖G存在,visit的頂點(diǎn)的應(yīng)用函數(shù)操作成果:對(duì)圖進(jìn)行深度優(yōu)先遍歷,在遍歷過(guò)程中對(duì)每個(gè)結(jié)點(diǎn)調(diào)用visit函數(shù)一次,一旦visit失敗,則操作失敗BFSTraverse(G,visit())初始條件:圖G存在,visit的頂點(diǎn)的應(yīng)用函數(shù)操作成果:對(duì)圖進(jìn)行廣度優(yōu)先遍歷,在遍歷過(guò)程中對(duì)每個(gè)結(jié)點(diǎn)調(diào)用visit函數(shù)一次,一旦visit失敗,則操作失敗}ADTGraph2、設(shè)定棧的抽象數(shù)據(jù)類型：ADTStack{數(shù)據(jù)對(duì)象：D={ai|ai∈CharSet，i=1，2，……，n，n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2，……，n}基本操作：InitStack(&S)操作成果：構(gòu)造一種空棧S。DestroyStack(&S)初始條件：棧S已存在。操作成果：棧S被銷毀。Push(&S,e);初始條件：棧S已存在。操作成果：在棧S的棧頂插入新的棧頂元素e。Pop(&S,e);初始條件：棧S已存在。操作成果：刪除S的棧頂元素，并以e返回其值。StackEmpty(S)初始條件：棧S已存在。操作成果：若S為空棧，則返回TRUE，否則返回FALSE。}ADTStack3、設(shè)定隊(duì)列的抽象數(shù)據(jù)類型：ADTQueue{數(shù)據(jù)對(duì)象:D={ai|ai屬于Elemset,i=1,2….,n,n>=0}數(shù)據(jù)關(guān)系:R1={<ai-1,ai>|ai-1,ai屬于D,i=1,2,…,n}約定ai為端為隊(duì)列頭,an為隊(duì)列尾基本操作:InitQueue(&Q)操作成果:構(gòu)造一種空隊(duì)列QDestryoQueue(&Q)初始條件：隊(duì)列Q已存在。操作成果：隊(duì)列Q被銷毀，不再存在。EnQueue(&Q,e)初始條件:隊(duì)列Q已經(jīng)存在操作成果:插入元素e為Q的新的隊(duì)尾元素DeQueue(&Q,&E)初始條件:Q為非空隊(duì)列操作成果:刪除Q的隊(duì)尾元素,并用e返回其值QueueEmpty(Q)初始條件:隊(duì)列已經(jīng)存在操作成果:若隊(duì)列為空,則返回TRUE,否則返回FLASE}ADTQueue4、本程序包括九個(gè)模塊：主程序模塊voidmain(){手動(dòng)構(gòu)造一種圖；從文獻(xiàn)導(dǎo)入一種圖；顯示圖的信息；進(jìn)行深度優(yōu)先遍歷圖；進(jìn)行廣度優(yōu)先遍歷圖；保留圖到一種文獻(xiàn)；尋找途徑；銷毀一種圖；}；手動(dòng)構(gòu)造一種圖-自己輸入圖的頂點(diǎn)和邊生成一種圖；從文獻(xiàn)導(dǎo)入一種圖；顯示圖的信息-打印圖的所有頂點(diǎn)和邊；進(jìn)行深度優(yōu)先遍歷圖-打出遍歷的結(jié)點(diǎn)序列和邊集；進(jìn)行廣度優(yōu)先遍歷圖-打出遍歷的結(jié)點(diǎn)序列和邊集；保留圖到一種文獻(xiàn)；尋找從起點(diǎn)到終點(diǎn)，但中間不通過(guò)某點(diǎn)的所有簡(jiǎn)樸途徑；銷毀圖。三、詳細(xì)設(shè)計(jì)頂點(diǎn),邊和圖類型#defineMAX_INFO10/*有關(guān)信息字符串的最大長(zhǎng)度+1*/#defineMAX_VERTEX_NUM20/*圖中頂點(diǎn)數(shù)的最大值*/typedefcharInfoType;/*有關(guān)信息類型*/typedefcharVertexType;/*字符類型*/typedefenum{unvisited,visited}VisitIf;typedefstructEBox{VisitIfmark;/*訪問(wèn)標(biāo)識(shí)*/intivex,jvex;/*該邊依附的兩個(gè)頂點(diǎn)的位置*/structEBox*ilink,*jlink;/*分別指向依附這兩個(gè)頂點(diǎn)的下一條邊*/InfoType*info;/*該邊信息指針*/}EBox;typedefstruct{VertexTypedata;EBox*firstedge;/*指向第一條依附該頂點(diǎn)的邊*/}VexBox;typedefstruct{VexBoxadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;/*無(wú)向圖的目前頂點(diǎn)數(shù)和邊數(shù)*/}AMLGraph;圖的基本操作如下：intLocateVex(AMLGraphG,VertexTypeu)；//查G和u有相似特性的頂點(diǎn)，若存在則返回該頂點(diǎn)在無(wú)向圖中位置;否則返回-1。VertexType&GetVex(AMLGraphG,intv)；//以v返回鄰接多重表中序號(hào)為i的頂點(diǎn)。intFirstAdjVex(AMLGraphG,VertexTypev)；//返回v的第一種鄰接頂點(diǎn)的序號(hào)。若頂點(diǎn)在G中沒(méi)有鄰接頂點(diǎn),則返回-1。intNextAdjVex(AMLGraphG,VertexTypev,VertexTypew)；//返回v的(相對(duì)于w的)下一種鄰接頂點(diǎn)的序號(hào)若w是v的最終一種鄰接點(diǎn),則返回-1。voidCreateGraph(AMLGraph&G)；//采用鄰接多重表存儲(chǔ)構(gòu)造,構(gòu)造無(wú)向圖G。StatusDeleteArc(AMLGraph&G,VertexTypev,VertexTypew)；//在G中刪除邊<v,w>。StatusDeleteVex(AMLGraph&G,VertexTypev)；//在G中刪除頂點(diǎn)v及其有關(guān)的邊。voidDestroyGraph(AMLGraph&G)；//銷毀一種圖voidDisplay(AMLGraphG)；//輸出無(wú)向圖的鄰接多重表G。voidDFSTraverse(AMLGraphG,VertexTypestart,int(*visit)(VertexType))；//從start頂點(diǎn)起,（運(yùn)用棧非遞歸）深度優(yōu)先遍歷圖G。voidBFSTraverse(AMLGraphG,VertexTypestart,int(*Visit)(VertexType))；//從start頂點(diǎn)起,廣度優(yōu)先遍歷圖G。voidMarkUnvizited(AMLGraphG)；//置邊的訪問(wèn)標(biāo)識(shí)為未被訪問(wèn)。其中部分操作的偽碼算法如下：voidCreateGraph(AMLGraph&G){/*采用鄰接多重表存儲(chǔ)構(gòu)造,構(gòu)造無(wú)向圖G*/DestroyGraph(G);/*假如圖不空,先銷毀它*/輸入無(wú)向圖的頂點(diǎn)數(shù)G.vexnum；輸入無(wú)向圖的邊數(shù)G.edgenum；輸入頂點(diǎn)的信息IncInfo；依次輸入無(wú)向圖的所有頂點(diǎn)；for(k=0;k<G.edgenum;++k)/*構(gòu)造表結(jié)點(diǎn)鏈表*/{讀入兩個(gè)頂點(diǎn)va、vb；i=LocateVex(G,va);/*一端*/j=LocateVex(G,vb);/*另一端*/p=(EBox*)malloc(sizeof(EBox));p->mark=unvisited;/*設(shè)初值*/p->ivex=i;p->jvex=j;p->info=NULL;p->ilink=G.adjmulist[i].firstedge;/*插在表頭*/G.adjmulist[i].firstedge=p;p->jlink=G.adjmulist[j].firstedge;/*插在表頭*/G.adjmulist[j].firstedge=p;}}voidDisplay(AMLGraphG){/*輸出無(wú)向圖的鄰接多重表G*/MarkUnvizited(G);輸出無(wú)向圖的所有頂點(diǎn)；for(i=0;i<G.vexnum;i++){p=G.adjmulist[i].firstedge;while(p)if(p->ivex==i)/*邊的i端與該頂點(diǎn)有關(guān)*/ { if(!p->mark)/*只輸出一次*/ { cout<<G.adjmulist[i].data<<'-'<<G.adjmulist[p->jvex].data<<ends; p->mark=visited; } p=p->ilink; }else/*邊的j端與該頂點(diǎn)有關(guān)*/ { if(!p->mark)/*只輸出一次*/ { cout<<G.adjmulist[p->ivex].data<<'-'<<G.adjmulist[i].data<<ends; p->mark=visited; } p=p->jlink;}cout<<endl;}}voidDFSTraverse(AMLGraphG,VertexTypestart,int(*visit)(VertexType)){/*從start頂點(diǎn)起,深度優(yōu)先遍歷圖G(非遞歸算法)*/InitStack(S);w=LocateVex(G,start);/*先確定起點(diǎn)start在無(wú)向圖中的位置*/for(v=0;v<G.vexnum;v++)Visited[v]=0;/*置初值*/for(v=0;v<G.vexnum;v++)if(!Visited[(v+w)%G.vexnum]){Push(S,(v+w)%G.vexnum);/*未訪問(wèn)，就進(jìn)棧*/while(!StackEmpty(S)){Pop(S,u);if(!Visited[u]){Visited[u]=1; /*未訪問(wèn)的標(biāo)志設(shè)為訪問(wèn)狀態(tài)，并輸出它的值*/visit(G.adjmulist[u].data);for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0; w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data)) if(!Visited[w]) Push(S,w);}}}DestroyStack(S);/*銷毀棧,釋放其空間*/}voidBFSTraverse(AMLGraphG,VertexTypestart,int(*Visit)(VertexType)){/*從start頂點(diǎn)起,廣度優(yōu)先遍歷圖G*/for(v=0;v<G.vexnum;v++)Visited[v]=0;/*置初值*/InitQueue(Q);z=LocateVex(G,start);/*先確定起點(diǎn)start在無(wú)向圖中的位置*/for(v=0;v<G.vexnum;v++)if(!Visited[(v+z)%G.vexnum])/*v尚未訪問(wèn)*/{Visited[(v+z)%G.vexnum]=1;/*設(shè)置訪問(wèn)標(biāo)志為TRUE(已訪問(wèn))*/Visit(G.adjmulist[(v+z)%G.vexnum].data);EnQueue(Q,(v+z)%G.vexnum);while(!QueueEmpty(Q))/*隊(duì)列不空*/ { DeQueue(Q,u); for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data)) if(!Visited[w]) { Visited[w]=1; Visit(G.adjmulist[w].data); EnQueue(Q,w); } }}DestroyQueue(Q);/*銷毀隊(duì)列,釋放其占用空間*/}2、棧類型#defineSTACK_INIT_SIZE100/*存儲(chǔ)空間初始分量*/#defineSTACKINCREMENT10/*存儲(chǔ)空間分派增量*/typedefintSElemType;typedefstruct{SElemType*base;SElemType*top;/*棧頂指針*/intstacksize;}SqStack;棧的基本操作如下：StatusInitStack(SqStack&S)；//構(gòu)造一種空棧S。StatusDestroyStack(SqStack&S)；//銷毀棧S(無(wú)論空否均可)。StatusPush(SqStack&S,SElemTypee)；//在S的棧頂插入新的棧頂元素e。StatusPop(SqStack&S,SElemType&e)；//刪除S的棧頂元素并以e帶回其值。StatusStackEmpty(SqStackS)；//若S為空棧，則返回TRUE，否則返回FALSE。3、隊(duì)列類型typedefintQelemType；typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;/*隊(duì)頭、隊(duì)尾指針*/}LinkQueue;隊(duì)列的基本操作如下：StatusInitQueue(LinkQueue&Q)；//構(gòu)造一種空隊(duì)列Q。StatusDestroyQueue(LinkQueue&Q)；//銷毀隊(duì)列Q(無(wú)論空否均可)。StatusQueueEmpty(LinkQueueQ)；//若Q為空隊(duì)列,則返回1,否則返回-1。StatusEnQueue(LinkQueue&Q,QElemTypee)；//插入元素e為Q的新的隊(duì)尾元素。StatusDeQueue(LinkQueue&Q,QElemType&e)；//若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回1,否則返回-1。4、生成樹類型:typedefstructCSNode{VertexTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;/*樹的二叉鏈表(孩子-兄弟)存儲(chǔ)構(gòu)造*/生成樹的操作：voidDFSTree(AMLGraphG,intv,CSTree&DT)；//從第v個(gè)頂點(diǎn)出發(fā)深度遍歷圖G,建立以DT為根的生成樹。voidDFSForest(AMLGraphG,VertexTypestart,CSTree&DT)；//建立圖G的深度優(yōu)先生成森林的(最左)孩子(右)兄弟鏈表DT。voidPrintTraverse(CSTreeT)；//打印圖G的遍歷生成樹的邊。voidPrintAllTraverse(CSTreeT)//打印圖G的遍歷生成森林的邊。voidBFSTree(AMLGraphG,intv,CSTree&BT)；//從第v個(gè)頂點(diǎn)出發(fā)廣度遍歷圖G,建立以BT為根的生成樹。voidBFSForest(AMLGraphG,VertexTypestart,CSTree&BT)；//建立圖G的廣度優(yōu)先生成森林的(最左)孩子(右)兄弟鏈表BT。voidPrintCSTree(CSTreeT,inti)；//用凹入表方式打印一棵以孩子-兄弟鏈表為存儲(chǔ)構(gòu)造的樹。voidPrintCSForest(CSTreeT)；//用凹入表方式打印一棵以孩子-兄弟鏈表為存儲(chǔ)構(gòu)造的森林。其中部分操作的偽碼算法如下：voidDFSTree(AMLGraphG,intv,CSTree&DT){/*從第v個(gè)頂點(diǎn)出發(fā)深度遍歷圖G,建立以DT為根的生成樹*/first=1;Visited[v]=1;for(w=FirstAdjVex(G,G.adjmulist[v].data);w>=0;w=NextAdjVex(G,G.adjmulist[v].data,G.adjmulist[w].data))if(!Visited[w]){p=(CSTree)malloc(sizeof(CSNode));/*分派孩子結(jié)點(diǎn)*/strcpy(p->data,G.adjmulist[w].data);p->firstchild=NULL;p->nextsibling=NULL;if(first)/*w是v的第一種未被訪問(wèn)的鄰接頂點(diǎn)是根的左孩子結(jié)點(diǎn)*/ { DT->firstchild=p; first=0; }else/*w是v的其他未被訪問(wèn)的鄰接頂點(diǎn)是上一鄰接頂點(diǎn)的右兄弟結(jié)點(diǎn)*/ q->nextsibling=p;q=p;DFSTree(G,w,q);/*從第w個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G,建立子生成樹q*/}}voidBFSTree(AMLGraphG,intv,CSTree&BT){/*從第v個(gè)頂點(diǎn)出發(fā)廣度遍歷圖G,建立以BT為根的生成樹*/r=BT;i=j=0;Visited[v]=1;InitQueue(Q);EnQueue(Q,v);/*先把第一種頂點(diǎn)入隊(duì)列*/while(!QueueEmpty(Q)){first=1;DeQueue(Q,u);for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))if(!Visited[w]){Visited[w]=1;p=(CSTree)malloc(sizeof(CSNode));strcpy(p->data,G.adjmulist[w].data);p->firstchild=NULL;p->nextsibling=NULL;if(first)/*w是v的第一種未被訪問(wèn)的鄰接頂點(diǎn)是根的左孩子結(jié)點(diǎn)*/ { r->firstchild=p; first=0; }else/*w是v的其他未被訪問(wèn)的鄰接頂點(diǎn)是上一鄰接頂點(diǎn)的右兄弟結(jié)點(diǎn)*/ q->nextsibling=p; cur[i++]=p;/*用一種數(shù)組指針保留生成樹的根*/ q=p; EnQueue(Q,w); }r=cur[j++];/*回朔到上一棵生成樹的根*/}DestroyQueue(Q);}voidPrintCSTree(CSTreeT,inti){/*用凹入表方式打印一棵以孩子-兄弟鏈表為存儲(chǔ)構(gòu)造的樹*/for(j=1;j<=i;j++)cout<<ends<<ends;/*留出i個(gè)空格以體現(xiàn)層*/cout<<T->data<<endl;/*打印元素,換行*/for(p=T->firstchild;p;p=p->nextsibling)PrintCSTree(p,i+1);/*打印子樹*/}voidPrintCSForest(CSTreeT){/*用凹入表方式打印一棵以孩子-兄弟鏈表為存儲(chǔ)構(gòu)造的森樹*/for(p=T;p;p=p->nextsibling){cout<<"第"<<i++<<"個(gè)樹:"<<endl;PrintCSTree(p,0);}}5、主程序和其他偽碼算法voidmain(){顯示菜單；輸入功能選擇鍵；switch(flag){case1:手動(dòng)構(gòu)造一種圖；case2:從文獻(xiàn)導(dǎo)入一種圖；case3:顯示圖的信息；case4:進(jìn)行深度優(yōu)先遍歷圖；case5:進(jìn)行廣度優(yōu)先遍歷圖；case6:保留圖到一種文獻(xiàn)；case7:尋找途徑；case8:銷毀圖；case9:退出程序；}銷毀圖；}intVisited[MAX_VERTEX_NUM];/*訪問(wèn)標(biāo)志數(shù)組(全局量)*/voidAllPath(AMLGraphG,VertexTypestart,VertexTypenopass,VertexTypeend,intk){/*尋找途徑*/Path[k]=start;/*加入目前途徑中*/l=LocateVex(G,nopass);u=LocateVex(G,start);Visited[u]=1;if(start==end)/*找到了一條簡(jiǎn)樸途徑*/{cout<<Path[0];for(i=1;Path[i];i++)cout<<"->"<<Path[i];/*打印輸出*/cout<<endl;}elsefor(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data)){if(w==l)continue;/*假如找到那個(gè)不想通過(guò)的點(diǎn),就繞過(guò)它,相稱不執(zhí)行背面的語(yǔ)句*/if(!Visited[w]) { temp=G.adjmulist[w].data; AllPath(G,temp,nopass,end,k+1);/*繼續(xù)尋找*/ }}Visited[u]=0;Path[k]=0;/*回溯*/}voidSaveGraph(AMLGraphG)/*保留圖的信息*/{建立輸出文獻(xiàn)流對(duì)象outgraph；輸入文獻(xiàn)名fileName；outgraph.open(fileName,ios::out);連接文獻(xiàn),指定打開方式if(!outgraph)/*調(diào)用重載算符函數(shù)測(cè)試流*/{cerr<<"文獻(xiàn)不能打開."<<endl;abort();}向流插入數(shù)據(jù)；outgraph.close();/*關(guān)閉文獻(xiàn)*/}voidLoadGraph(AMLGraph&G){建立輸入文獻(xiàn)流對(duì)象ingraph；輸入文獻(xiàn)名fileName；if(!ingraph){cerr<<"文獻(xiàn)不能打開."<<endl;abort();}向流輸出數(shù)據(jù)；ingraph.close();/*關(guān)閉文獻(xiàn)*/}visit(VertexTypev){/*輸出結(jié)點(diǎn)*/cout<<v<<ends;returnOK;}voidmessage()/*菜單顯示*/{cout<<"\n\t\t********************\n";cout<<"\t\t*\t1:手動(dòng)構(gòu)造一種圖\t*\n";cout<<"\t\t*\t2:從文獻(xiàn)導(dǎo)入一種圖\t*\n";cout<<"\t\t*\t3:顯示圖的信息\t*\n";cout<<"\t\t*\t4:進(jìn)行深度優(yōu)先遍歷圖\t*\n";cout<<"\t\t*\t5:進(jìn)行廣度優(yōu)先遍歷圖\t*\n";cout<<"\t\t*\t6:保留圖到一種文獻(xiàn)\t*\n";cout<<"\t\t*\t7:尋找途徑\t*\n";cout<<"\t\t*\t8:銷毀圖\t*\n";cout<<"\t\t*\t9:退出程序\t\t*\n";cout<<"\t\t********************\n";}四、調(diào)試分析1、本程序以鄰接多重表為存儲(chǔ)構(gòu)造。這個(gè)程序波及到圖的生成和圖的深度以及廣度遍歷,文獻(xiàn)的保留和讀取，尚有棧和隊(duì)列的操作，此外尚有森林的生成和打印，途徑的尋找。2、本程序不僅可以進(jìn)行連通無(wú)向圖的遍歷，還可以進(jìn)行非連通圖的遍歷。為了以便顯示和理解，目前暫且用一種大寫字母表達(dá)一種頂點(diǎn)。邊還可以附加信息，但為了以便操作，暫且不輸入信息。已經(jīng)先把圖的有關(guān)信息保留在了文本文檔里，因此要測(cè)試時(shí)直接從文獻(xiàn)導(dǎo)入，可以減少用手輸入的麻煩，同步也可以減少輸入的錯(cuò)誤。3、由于構(gòu)造圖時(shí)，后輸入的邊是插在先輸入的邊的前面。因此在輸入邊時(shí)，可以按字母從大到小的次序輸入。那么顯示圖的時(shí)候就可以按字母從小到大的次序顯示。4、程序定義了一種二倍頂點(diǎn)長(zhǎng)的數(shù)組寄存輸入的邊，以便程序可以把它保留到文獻(xiàn)里。故花費(fèi)了一定的內(nèi)存空間。五、顧客手冊(cè)1、本程序的運(yùn)行環(huán)境DOS操作系統(tǒng)，GTraverse.exe2、選擇操作1：程序就提醒分別輸入無(wú)向圖的頂點(diǎn)數(shù)，邊數(shù)，邊的信息，頂點(diǎn)和邊的值：輸入完畢后，程序提醒按任一鍵返回菜單：3、選擇操作2：程序提醒輸入一種存有圖信息文獻(xiàn)的途徑去導(dǎo)入一種圖：假如導(dǎo)入成功，它會(huì)顯示導(dǎo)入成功，并提醒按任一鍵返回。4、選擇操作3：程序顯示圖的頂點(diǎn)和邊的信息。5、選擇操作4：系統(tǒng)提醒輸入遍歷圖的起始點(diǎn)，程序運(yùn)行后，首先顯示深度優(yōu)先遍歷的訪問(wèn)結(jié)點(diǎn)序列和生成樹的邊集。然后再提醒按任一鍵繼續(xù)顯示深度優(yōu)先遍歷的生成森林。6、選擇操作5：系統(tǒng)提醒輸入遍歷圖的起始點(diǎn)，程序運(yùn)行后，首先顯示廣度優(yōu)先遍歷的訪問(wèn)結(jié)點(diǎn)序列和生成樹的邊集。然后再提醒按任一鍵繼續(xù)顯示廣度優(yōu)先遍歷的生成森林。7、選擇操作6：程序會(huì)提醒輸入要寄存圖信息的文獻(xiàn)的途徑：8、選擇操作7：程序會(huì)提醒輸入途徑遍歷的起點(diǎn)start，終點(diǎn)end，不想通過(guò)的點(diǎn)nopass。9、選擇操作8：銷毀一種圖。10、選擇操作9：退出程序。六、測(cè)試成果選擇操作1，分別進(jìn)行如下操作：請(qǐng)輸入圖的節(jié)點(diǎn)數(shù)(EG.G.vexnum=10):8請(qǐng)輸入圖的邊數(shù)(EG.G.edgenum=4):9請(qǐng)輸入8個(gè)節(jié)點(diǎn)的表達(dá)值:ABCDEFGH請(qǐng)輸入有序的邊(用空格作間隔):FGEHDHCGCFBEBDACAB2)選擇操作3，輸出圖的信息如下：這個(gè)圖有8葉子:ABCDEFGH這個(gè)圖有9邊:A-BA-CB-DB-EC-FC-GD-HE-HF-G3）選擇操作4，輸入遍歷起點(diǎn)，如A（也可以輸入B，C……）*****深度優(yōu)先遍歷圖的成果*****深度優(yōu)先遍歷的訪問(wèn)結(jié)點(diǎn)序列:ACGFBEHD深度優(yōu)先遍歷生成樹的邊集:A-BB-DD-HH-EA-CC-FF-G深度優(yōu)先遍歷的生成森林:第1個(gè)樹:ABDHECF