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

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

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

4、請運行程序，如有可能，請你盡力為代碼寫注釋。將運行結(jié)果寫在實驗報告中。選作：請你自己任意在教材上選取一個無向圖，并在程序中按照你選取的無向圖修改程序，運行程序，觀察輸出的鄰接表結(jié)果）5程序及測試結(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);運行結(jié)果：6實驗分析與體會 通過本次實驗，使我掌握了圖的兩種