图遍历的演示

1、 数据结构课程实验报告 题目：图遍历的演示 班级： 姓名： 学号： 专业： 学院： 完成日期：1、 需求分析（1） 问题描述： 很多涉及图上操作的算法都是以图的遍历操作作为基础的。试写一个程序，演示在连通图的无向图上访问全部结点的操作。（2） 基本要求：以邻接多重表（选作内容邻接表）为存储结构，实现连通无向图的深度优先遍历和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集（3） 输入的形式和输入的范围：先输入顶点数N以及边数M，然后依次输入N个顶点，再按提示输入M条边的信息用（a-b 3）类似的形式（4） 测试数据：教科书图7.33部分信息2、 概要设计

2、（1） 抽象数据类型图的定义：ADT Graph 数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。 数据关系 R: R=VR VR= <v,w>| v,w V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息 基本操作 P： locatevex(G, mes)； 初始条件：图G存在，mes和G中顶点有相同的特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。 createudn( & G)； 初始条件：图G 存在。 操作结果：创建无向图。 createdn( & G

3、)； 初始条件：图G 存在。 操作结果：创建有向图。 createudg( & G)； 初始条件：图G 存在 操作结果：创建无向网。 createdg(& G)； 初始条件：图G 存在。 操作结果：创建有向网。 DFS(G,v)； 初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。 操作结果：深度优先搜索遍历图G，访问顶点时使用函数visit. BFS(G,v)； 初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。 操作结果：广度优先搜索遍历图G，访问顶点时使用函数visit. visit( a)； 初始条件：a为图中的某个顶点值。 操作结果：访问顶点a，本

4、程序中作用结果为输出顶点值。 ADT Graph （2） .邻接表存储结构的图定义： ADT algraph 数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。 数据关系 R: R=VR VR= <v,w>| v,w V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息 基本操作 P： locatevex(G, mes)； 初始条件：图G存在，mes和G中顶点有相同的特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。 createudn( & G)； 初始条件：图G 存在。

5、 操作结果：创建无向图。 createdn( & G)； 初始条件：图G 存在。 操作结果：创建有向图。 Createudg( & G)； 初始条件：图G 存在。 操作结果：创建无向网。 createdg(& G)； 初始条件：图G 存在。 操作结果：创建有向网。 DFS(G,v)； 初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。 操作结果：深度优先搜索遍历图G，访问顶点时使用函数visit. BFS(G,v)； 初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。 操作结果：广度优先搜索遍历图G，访问顶点时使用函数visit.visit( a)；

6、 初始条件：a为图中的某个顶点值。 操作结果：访问顶点a，本程序中作用结果为输出顶点值。 ADT algraph2. （3）设定队列的抽象数据类型定义：ADT Queue数据对象：D=ai|aiElemSet, i=1,2, ,n, n0数据关系：R1=<ai-1,ai>|ai-1,aiD, i=1,2, ,n 约定a1为队列头，an为队列尾。基本操作： InitQueue( &Q ) 操作结果：构造一个空队列Q。 DestroyQueue ( &Q ) 初始条件：队列Q已存在。 操作结果：销毁队列Q。 ClearQueue ( &Q ) 初始条件：队列Q已

7、存在。 操作结果：将Q清为空队列。 QueueEmpty( Q ) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 QueueLength( Q ) 初始条件：队列Q已存在。 操作结果：返回Q的数据元素个数，即队列的长度。 GetHead( Q, &e ) 初始条件：队列Q已存在且非空。 操作结果：用e返回Q的队头元素。 EnQueue( &Q, e ) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 DeQueue( &Q, &e ) 初始条件：队列Q已存在且非空。 操作结果：删除Q的队头元素，并用e

8、返回其值。QueueTraverse( Q, visit() ) 初始条件：队列Q已存在且非空。 操作结果：从队头到队尾依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ADT Queue3、 详细设计（1） 元素类型、结点类型和指针类型typedef struct /图的邻接矩阵存储结构 char *vexs; /顶点向量 int arcsMAX+1MAX+1; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和边数 Graph; （2） 队列的具体定义class Queue /队列类 public: void InitQueue() bas

9、e=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) /插入元素e为新的队尾元素 baserear=e; rear=(rear+1)%QUEUE_SIZE; /rear后移void DeQueue(int &e) /若队列不空，则删除对头元素，用e返回e=basefront; front=(front+1)%QUEUE_SIZE; public: int *base; int front; int rear; ; （3） 查找定位函数int Locate(Graph G,char c) /图G

10、中查找元素c的位置 for(int i=1;i<=G.vexnum;i+) if(G.vexsi=c) return i; return -1; （4） 初始化无向图函数void CreateUDN(Graph &G) /创建无向图 int i,j,w,s1,s2; char a,b,temp; cout<<"输入顶点的总数和边的总数:" cin>>G.vexnum>>G.arcnum; temp=getchar(); /接收回车 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分

11、配顶点数目 cout<<"输入"<<G.vexnum<<"个顶点分别为:"<<endl; for(i=1;i<=G.vexnum;i+) /初始化顶点 cout<<"顶点:"<<i; cin>>&G.vexsi;temp=getchar(); for(i=1;i<=G.vexnum;i+) /初始化邻接矩阵 for(j=1;j<=G.vexnum;j+) G.arcsij=INFINITY; /16int类型，初始化边为无穷大

12、 cout<<"输入"<<G.arcnum<<"条边分别为:"<<endl; /读取边信息并初始化集合 for(i=1;i<=G.arcnum;i+) /初始化边 cout<<"边"<<i<<endl; scanf("%c-%c %d",&a,&b,&w); /输入边和权值 temp=getchar(); /接收回车 s1=Locate(G,a); s2=Locate(G,b); G.arcss1s2=

13、G.arcss2s1=w; /无向 int FirstVex(Graph G,int k) /图G中顶点k的第一个邻接顶点 if(k>=1 && k<=G.vexnum) for(int i=1;i<=G.vexnum;i+) if(G.arcski!=INFINITY) return i; return -1; int NextVex(Graph G,int i,int j) /图G中顶点i的第j个邻接顶点的下一个邻接顶点if(i>=1 && i<=G.vexnum && j>=1 && j&

14、lt;=G.vexnum) /i,j合理 for(int k=j+1;k<=G.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1; （5） 深度优先遍历及广度优先遍历函数void DFS(Graph G,int k) /深度优先搜索 int i; if(k=-1) /第一次执行DFS时,k为-1 for(i=1;i<=G.vexnum;i+) if(!visitedi) DFS(G,i); /对尚未访问的顶点调用DFS else visitedk=true; /访问第k个顶点 cout<<G.vexsk; for

15、(i=FirstVex(G,k);i>=1;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); void BFS(Graph G) /广度优先搜索 int k; Queue Q; /辅助队列Q Q.InitQueue(); for(int i=0;i<=G.vexnum;i+) if(!visitedi) /i尚未访问 visitedi=true; cout<<G.vexsi; Q.EnQueue(i); /i入列 while(Q.front!=Q.rear) Q.DeQueue(k); /队头元素出列并置为k for(int w=Firs

16、tVex(G,k);w>=0;w=NextVex(G,k,w) if(!visitedw) /w为k的尚未访问的邻接顶点 visitedw=true; cout<<G.vexsw; Q.EnQueue(w); （6） 主函数void main() /主函数 int i; Graph G; CreateUDN(G); /创建无向图 visited=(bool *)malloc(G.vexnum*sizeof(bool); cout<<endl<<"深度优先搜索结果为:" for(i=1;i<=G.vexnum;i+) visitedi=false; /标志数组初始化为false DFS(G,-1); c