实验五 图的基本操作

1、实验五 图的基本操作一、 实验目的1、 使学生可以巩固所学的有关图的基本知识。2、 熟练掌握图的存储结构。3、 熟练掌握图的两种遍历算法。二、 实验内容本次实验提供两个题目，难度相当，学生可以根据自己的情况选做，其中题目一是必做题，其他选做！题目一：图的遍历（必做）问题描述对给定图，实现图的深度优先遍历和广度优先遍历。基本要求以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。测试数据由学生依据软件工程的测试技术自己确定。题目二：在图G中求一条从顶点i到顶点s的简单路径测试数据自行设计题目三：在图G中求一条从顶点i到顶点s且长度为K的简单路径测试数据自行设计三、 算法设计1、 主要思想：首先定义邻接表存储结构，然后创建一个空队列，进行队列的进队，出对和判空操作，然后建立邻接表，接着进行图的深度优先遍历和广度遍历，最后编写主函数。对于邻接表，是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在

2、图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息。每个链表上附设一个表头结点。infonextarcadjvex表结点： firstarcdata 头结点： 对于图的深度优先遍历DFS，类似于树的先根遍历，是树的先跟遍历的推广，是一个递归算法； 对于图的广度优先遍历BFS，类似于树的层次遍历，不是递归算法。2、 本程序包含6个模块（1） 主函数void main()定义图，输出图的深度优先遍历和广度优先遍历结果；（2） 队列的构造：包括队列的初始化、进队、出对和判空，int InitQueue（）；int EnQueue（）；int DeQueue（）；int QueueEmpty（）。（3） 邻接表的建立void GreatGraph（）；（4） 图的深度优先遍历void DFS（）；（5） 图的广度优先遍历void BFS（）；3、 元素类型和结点类型typedef struct ArcNodeint adjvex;struct ArcNode * nextarc;int info;ArcNode;typedef struct VN

3、odechar date;ArcNode * firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;ALGraph;typedef struct QNodechar data;struct QNode *next;QNode,*QueuePtr;typedef struct /构造一个空队列QueuePtr front; QueuePtr rear;LinkQueue;4、 主函数和其他函数清单（1） int InitQueue（）：初始化队列；（2） int EnQueue（）：进队；（3） int DeQueue（）：出对；（4） int QueueEmpty（）：队列的判空（5） void GreatGraph（）：建立邻接表；（6） void DFS（）：深度优先遍历；（7） void BFS（）：广度优先遍历；（8） void main（）：主函数。四、 调试分析算法设计欠周全，在编写输出两条边的信息的时候，不能一次性输入完毕，必须得输入两个顶点后才能接着输入

4、下一顶点信息，比较繁琐，不够简洁，如果顶点够多的话，比较花费时间；对输入的数据有了一定的考虑，如果输入的数据不合理，也就不能正确输出；刚开始时给数据赋初值有错，以后的多注意。五、 实验结果利用课本第168页图7.13（a）图的数据进行测试六、 总结对于这次实验，心里面一直很担心，因为实验都快做完了，我还一次都没有让老师检查过，然后时间上有特别的紧张，知道要做实验了，就一遍又一遍的去看书上相关的算法，上网查询，还有问了别的同学，最后才勉勉强强的将它给弄出来了。在让老师检查的时候，特别的紧张，话都说不利索了，很开心，但是还是有很多的不足之处，还是得好好的多看书，把基础知识给弄透彻。我争取下次还把实验给做出来。七、 源程序#include#include#include#define MAX_VERTEX_NUM 20typedef struct ArcNodeint adjvex;struct ArcNode * nextarc;int info;ArcNode;typedef struct VNodechar date;ArcNode * firstarc;VNode,AdjListMA

5、X_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;ALGraph;typedef struct QNodechar data;struct QNode *next;QNode,*QueuePtr;typedef struct /构造一个空队列QueuePtr front; QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q)Q.front =Q.rear =new QNode;if(!Q.front ) exit(-1);Q.front -next =NULL;return 0;int EnQueue(LinkQueue &Q,int e) QueuePtr p;p=new QNode;if(!p) exit(-1);p-data=e;p-next=NULL;Q.rear-next =p;Q.rear =p;return 0;int DeQueue(LinkQueue &Q,int &e)QueuePtr p;if(Q.front =Q.rear ) return

6、 0;p=Q.front -next ;e=p-data;Q.front -next =p-next;if(Q.rear =p) Q.rear =Q.front ;free(p);return 0;int QueueEmpty(LinkQueue &Q)if(Q.front =Q.rear ) return 1;elsereturn 0;int Locatevex(ALGraph &G,char v)int k,j=0;for(k=0;kG.vexnum ;k+)if(G.vertices k.date =v)j=k;break;return j;void GreatGraph(ALGraph &G) /建立邻接表int k;char tail,head;int i,j;cout输入顶点数和弧数G.vexnum G.arcnum ; cout输入顶点信息endl;for( i=0;iG.vertices i.date ;G.vertices i.firstarc =NULL;cout输入边的信息：endl;for(k=0;kG.arcnum ;k+) cout输入两条边的信息tailh

7、ead;j=Locatevex(G,head);i=Locatevex(G,tail);ArcNode *p=new ArcNode;p-adjvex =j;p-nextarc =G.vertices i.firstarc ;G.vertices i.firstarc =p;ArcNode *q=new ArcNode;q-adjvex =i;q-nextarc =G.vertices j.firstarc ;G.vertices j.firstarc =q;int FirstAdjVex(ALGraph G,int v)/返回v的第一个邻接顶点 if(G.verticesv.firstarc) return G.verticesv.firstarc-adjvex; else return -1;int NextAdjVex(ALGraph G,int v,int w)/返回v中相对于w的下一个邻接顶点 int flag=0; ArcNode *p; p=G.verticesv.firstarc; while(p) if(p-adjvex=w) flag=1; break; p=p-nextarc; if(flag & p-nextarc) return p-nextarc-adjvex; else return -1;/深度优先遍历int visited30;void DFS(ALGraph &G,int v)visitedv=1;coutG.verticesv.date=0;w=NextAdjVex(G,v,w)if(!visitedw) DFS(G,w);void DFSTraverse(ALGraph &G) int v; for(v=0;vG.vexnum;+v) visitedv=0; for(v=0;vG.vexnum;+v) if(!visitedv) DFS(G,v); int ( *visit)(int v);void BFS(ALGraph &G)/广度优先遍历int v; LinkQueue Q; int w;for(v=0;vG.vexnum;+v)visitedv=0;InitQueue

《实验五 图的基本操作》由会员我***分享，可在线阅读，更多相关《实验五 图的基本操作》请在金锄头文库上搜索。