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

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

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

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