图的存储结构和遍历实习报告

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实验分析与体会 通过本次实验，使我掌握了图的两种