圖的存儲(chǔ)結(jié)構(gòu)和遍歷實(shí)習(xí)報(bào)告

1、實(shí) 驗(yàn) 報(bào) 告學(xué)院： 計(jì)算機(jī)科學(xué)學(xué)院 專(zhuān)業(yè)： 計(jì)算機(jī)應(yīng)用 2012年12月15 日姓 名程咬金學(xué) 級(jí)計(jì)應(yīng)2班指導(dǎo)老師孔子課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)成績(jī)實(shí)驗(yàn)名稱(chēng)圖的存儲(chǔ)結(jié)構(gòu)和遍歷1實(shí)驗(yàn)?zāi)康恼莆請(qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)，鄰接矩陣存儲(chǔ)法和鄰接表存儲(chǔ)法了解圖的兩種存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)過(guò)程掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的方法了解圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的實(shí)現(xiàn)過(guò)程2實(shí)驗(yàn)內(nèi)容1. 采用圖的鄰接矩陣存儲(chǔ)方法，畫(huà)出上圖的鄰接矩陣2. 采用圖的鄰接表存儲(chǔ)方法，畫(huà)出上圖的鄰接表結(jié)構(gòu)3. 基于第2題的鄰接表，寫(xiě)出圖的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列4. 運(yùn)行程序Graph.cpp，了解圖的存儲(chǔ)方法和遍

2、歷算法的實(shí)現(xiàn)過(guò)程3實(shí)驗(yàn)環(huán)境操作系統(tǒng)： windows 7編譯器：VC+6.04實(shí)驗(yàn)方法和步驟（含設(shè)計(jì)）要求：正文五號(hào)字，行間距：最小值 0磅。段前0.5行，段后0,5行寫(xiě)出每個(gè)題目的解題思路。1. 解題思路：（請(qǐng)寫(xiě)出無(wú)向圖鄰接矩陣公式，并按公式畫(huà)出圖對(duì)應(yīng)的鄰接矩陣）鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣，設(shè)G=（V,E）是具有n（n>0）個(gè)頂點(diǎn)的圖，頂點(diǎn)的順序依次為（v0,v1,vn-1），則G的無(wú)向鄰接矩陣A是n階方陣，其定義如下：Aij=鄰接矩陣如下：G= 2.解題思路：（請(qǐng)畫(huà)出無(wú)向圖對(duì)應(yīng)的鄰接表存儲(chǔ)結(jié)構(gòu)）3.解題思路：（請(qǐng)寫(xiě)出深度優(yōu)先遍歷和廣度優(yōu)先遍歷的算法基本思想，并寫(xiě)出遍歷序列，

3、無(wú)需編寫(xiě)程序）深度優(yōu)先搜索遍歷的過(guò)程：從圖中某個(gè)初始頂點(diǎn)v出發(fā)，首先訪問(wèn)初始頂點(diǎn)V，然后選擇一個(gè)與頂點(diǎn)V相鄰且沒(méi)有被訪問(wèn)過(guò)的頂點(diǎn)W為初始頂點(diǎn)，在從W出發(fā)進(jìn)行深度優(yōu)先搜索，直到圖中與當(dāng)前頂點(diǎn)V相鄰的所有頂點(diǎn)都被訪問(wèn)過(guò)為止，這個(gè)過(guò)程是遞歸過(guò)程。以V1開(kāi)始深度優(yōu)先遍歷序列：v1 v2 v3 v5 v4 v6廣度優(yōu)先搜索遍歷的過(guò)程：首先訪問(wèn)初始點(diǎn)Vi，接著訪問(wèn)V的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)V1，V2，V3，V4，Vt，然后再按照其次序訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，以此類(lèi)推，直到圖中所有和初始點(diǎn)V有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)為止。以V1為初始點(diǎn)。廣度優(yōu)先遍歷：v1 v2 v4 v6 v3 v54.（

4、請(qǐng)運(yùn)行程序，如有可能，請(qǐng)你盡力為代碼寫(xiě)注釋。將運(yùn)行結(jié)果寫(xiě)在實(shí)驗(yàn)報(bào)告中。選作：請(qǐng)你自己任意在教材上選取一個(gè)無(wú)向圖，并在程序中按照你選取的無(wú)向圖修改程序，運(yùn)行程序，觀察輸出的鄰接表結(jié)果）5程序及測(cè)試結(jié)果：#include <stdio.h>#include <stdlib.h>#define MAXV 10typedef structint no;int info;Vertex;typedef structint edgesMAXVMAXV;int n,e;Vertex vexsMAXV;MGraph;void matrix(MGraph &g)g.n=6;int

5、AMAXV=1,2,3,4,5,6;for(int i=0;i<g.n;i+)g.vexsi.no=Ai;g.e=9;int BMAXVMAXV=0,1,0,1,0,1,1,0,1,1,1,0,0,1,0,0,1,0,1,1,0,0,1,1,0,1,1,1,0,0,1,0,0,1,0,0;int j,k;for(j=0;j<g.n;j+)for(k=0;k<g.n;k+)g.edgesjk=Bjk;printf("%2d",g.edgesjk);printf(" ");printf("n");typedef stru

6、ct ANodeint adjvex;struct ANode *nextarc;int info;ArcNode;typedef struct VNodeVertex data;ArcNode *firstarc;VNode;typedef VNode AdjListMAXV;typedef structAdjList adjlist;int n,e;ALGraph;void MatToList(MGraph g,ALGraph *&G)int i,j,n=g.n;ArcNode *p;G=(ALGraph*)malloc(sizeof(ALGraph);for(i=0;i<n

7、;i+)G->adjlisti.data.no=g.vexsi.no;G->adjlisti.firstarc=NULL;for(i=0;i<n;i+)for(j=n-1;j>=0;j-)if(g.edgesij!=0)p=(ArcNode*)malloc(sizeof(ArcNode);p->adjvex=j+1;p->nextarc=G->adjlisti.firstarc;G->adjlisti.firstarc=p;G->n=n;G->e=g.e;void displayALGraph(ALGraph* g)int i;for

8、(i=0;i<g->n;i+)printf("%d: ",g->adjlisti.data.no);ArcNode* p=g->adjlisti.firstarc;if(p!=NULL)printf("%d ",p->adjvex);p=p->nextarc;while(p!=NULL)printf("%d ",p->adjvex);p=p->nextarc;printf("n");void main()MGraph g1;matrix(g1);ALGraph* g2;MatToList(g1,g2);printf("n");displayALGraph(g2);運(yùn)行結(jié)果：6實(shí)驗(yàn)分析與體會(huì) 通過(guò)本次實(shí)驗(yàn)，使我掌握了圖的兩種