圖遍歷的演示實習(xí)報告

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