图遍历 C++ 数据结构.doc

数据结构实验（五） 评分 :_专业 :计算机科学与技术班级 :计算机09-1姓名 :*指导老师 :陈* 完成时间 :2010-12-5实验五 图的遍历一、题目：（一）实习目的1、 掌握图的基本概念和邻接矩阵、邻接表的存储结构。2、 掌握图的邻接矩阵和邻接表的存储结构的算法实现。3、 掌握图在邻接矩阵和邻接表存储结构上遍历算法的实现。（二）实习内容1、 用邻接矩阵或邻接表实现深度优先搜索遍历。2、 用邻接矩阵或邻接表实现广度优先搜索遍历。2 161538471二、程序代码：#includeusing namespace std;const int MaxSize=8;class MGraphpublic:MGraph(int a,int n,int e);MGraph()int GetVex(int i);void DFSTraverse(int v);void BFSTraverse(int v);void Resetvisited();private:int vertexMaxSize;int arcMaxSizeMaxSize;int vertexNum,arcNum;int visitedMaxSize;MGraph:MGraph(int a,int n,int e)int i,j,k;vertexNum=n;arcNum=e;for(i=0;ivertexNum;i+)vertexi=ai;visitedi=0;for(i=0;ivertexNum;i+)for(j=0;jvertexNum;j+)arcij=0;cout请输入依次两两地输入有边的结点endl;for(k=0;kij;arcij=1;arcji=1;void MGraph:Resetvisited()int i;for(i=0;ivertexNum;i+)visitedi=0;void MGraph:DFSTraverse(int v)int j;coutvertexv ;visitedv=1;for(j=0;jvertexNum;j+)if(arcvj=1&visitedj=0)DFSTraverse(j);void MGraph:BFSTraverse(int v)int j,front,rear;int QMaxSize;front=rear=-1;coutvertexv ;visitedv=1;Q+rear=v;while(front!=rear)v=Q+front;for(j=0;jvertexNum;j+)if(arcvj=1&visitedj=0)coutvertexj ;visitedj=1;Q+rear=j;void main()int a8=1,2,3,4,5,6,7,8;MGraph g(a,8,15);cout深度优先遍历：;g.DFSTraverse(1);coutendlendl;g.Resetvisited();cout广度优先遍历：;g.BFSTraverse(1);coutendlendl;三、运行结果：四、实验心得：这次实验中，遇到的最大问题是控制访问过的visitedMaxSize 数组。初始时，未对其初始化，造成遍历失败。做实