數(shù)據(jù)結(jié)構(gòu)實驗報告-8

沈陽工程學院學生實驗報告實驗室名稱：信息工程系軟件實驗室實驗課程名稱：數(shù)據(jù)結(jié)構(gòu)實驗項目名稱：圖的結(jié)構(gòu)及多種應(yīng)用班級：計專本121姓名：鄭永凱學號：2012461127實驗日期：2013年5月17日實驗臺編號：17指導(dǎo)教師：代欽批閱教師（簽字）：成績：實驗?zāi)康?.掌握圖的存儲思想及其存儲實現(xiàn)。2.掌握圖的深度，廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。3.掌握圖的常見應(yīng)用算法的思想及其程序?qū)崿F(xiàn)。實驗內(nèi)容1.鍵盤輸入數(shù)據(jù)，建立一個有向圖的鄰接表或鄰接矩陣。2.輸出該鄰接表或鄰接矩陣。3.以有向圖的鄰接表或鄰接矩陣為基礎(chǔ)實現(xiàn)輸出它的拓撲排序序列。4.采用鄰接表或鄰接矩陣存儲實現(xiàn)圖的深度優(yōu)先遍歷。5.采用鄰接表或鄰接矩陣存儲實現(xiàn)圖的廣度優(yōu)先遍歷。6.采用鄰接矩陣存儲實現(xiàn)無向圖的最小生成樹的PRIM算法。7.在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。8.3和6是選做題實驗前的準備理解圖的存儲思想。理解圖的深度，廣度優(yōu)先遍歷算法思想。理解圖的常見應(yīng)用算法的思想。實驗要求及實驗軟硬件環(huán)境【基本要求】掌握圖的存儲思想。掌握圖的深度，廣度優(yōu)先遍歷算法思想。掌握圖的常見應(yīng)用算法的思想。完成此項實驗，完成實驗報告【實驗組織方式】個人實驗【實驗條件】Windows操作系統(tǒng)實驗過程及程序清單了解圖的結(jié)構(gòu)圖是一種數(shù)據(jù)結(jié)構(gòu)，由二個集合V和E組成，記做G=(V,E)，其中V是數(shù)據(jù)元素的非空有限集合，E是V中二元關(guān)系（邊）的集合。即V是頂點的集合，E是頂點的偶對，即邊的集合。根據(jù)E的性質(zhì)，圖可分為兩類：①有向圖：圖的每條邊都是有序頂點對（即邊是有方向的）②無向圖：圖的每條邊都是無序頂點對（即邊是無方向的）建立有向圖的鄰接矩陣代碼：typedefstruct{intvexnum,arcnum;/*當前圖的頂點數(shù)和邊或弧數(shù)*/VexTypevexs[N];/*圖中N個頂點的信息*/AdjTypearcs[N][N];/*圖鄰接矩陣信息。對無權(quán)圖，用0或1表示相鄰否；對帶權(quán)圖，則為權(quán)值類型*/}graph;voidCreatGraph(graph*ga)/*建立一個有向圖ga*/{inti,j,w;/*w表示是否鄰接*/charv;ga->vexnum=0;ga->arcnum=0;i=0; cout<<"讀入頂點信息"<<endl;while((v=getchar())!='#'){ga->vexs[i]=v;/*讀入頂點信息*/ i++;}ga->vexnum=i;/*頂點數(shù)目*/for(i=0;i<ga->vexnum;i++)/*鄰接矩陣初始化*/ for(j=0;j<ga->vexnum;j++)ga->arcs[i][j]=0; cout<<"讀入邊信息"<<endl;scanf("%d,%d,%d",&i,&j,&w);/*讀入邊(i,j)上的w*/while(i!=-1){ ga->arcs[i][j]=w; scanf("%d,%d,%d",&i,&j,&w);}其具體實現(xiàn)如下圖1所示：圖1創(chuàng)建有向圖鄰接矩陣3、顯示鄰接矩陣代碼： cout<<"顯示鄰接矩陣"<<endl; for(i=0;i<ga->vexnum;i++){ for(j=0;j<ga->vexnum;j++) cout<<ga->arcs[i][j]<<'\t'; cout<<endl; }其具體實現(xiàn)如圖2所示：圖2顯示鄰接矩陣4、選擇算法①深度優(yōu)先算法代碼：voiddfs(inti,graph*g){/*深度優(yōu)先搜索遞歸算法*/intj;printf("node:%c\n",g->vexs[i]);visited[i]=TRUE;for(j=0;j<g->vexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j]))dfs(j,g);}voidtdfs(graph*g){ ///*深度優(yōu)先搜索遍歷整圖算法*/inti;for(i=0;i<g->vexnum;i++)if(visited[i]!=TRUE)dfs(i,g);}具體實現(xiàn)如圖3所示：圖3深度優(yōu)先算法②廣度優(yōu)先算法代碼：typedefstruct{intrear,front;VexTypedata[N];}queue;voidbfs(intk,graph*g){inti,j;queueqlist,*q;q=&qlist;q->rear=0;q->front=0;printf("node:%c\n",g->vexs[k]);visited[k]=TRUE;q->data[q->rear++]=k;while(q->rear!=q->front){i=q->data[q->front++];for(j=0;j<g->vexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j])){printf("node:%c\n",g->vexs[j]);visited[j]=TRUE;q->data[q->rear++]=j;}}}voidtbfs(graph*g){inti;for(i=0;i<g->vexnum;i++)if(visited[i]!=TRUE)bfs(i,g);}具體實現(xiàn)如圖4所示：圖4廣度優(yōu)先算法結(jié)果分析本實驗所要實現(xiàn)的是圖的多種應(yīng)用，在實驗之前預(yù)先設(shè)計的有向圖為：按照深度優(yōu)先算法排列應(yīng)為：A→B→D→C,與