數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-8

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