资源预览内容
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
亲,该文档总共6页全部预览完了,如果喜欢就下载吧!
资源描述
华北水利水电学院 数据结构 实验报告20122013学年 第 二 学期 2012级(专升本) 计算机科学与技术 专业班级: 196 学号: 201219614 姓名: 吕竹青 实验四 图的应用一、 实验题目:图的应用深度优先广度优先搜索遍历二、 实验内容:很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法,实现图的深度优先和广度优先搜索遍历操作。要求:以邻接矩阵或邻接表为存储结构,以用户指定的顶点为起始点,实现连通无向图的深度优先及广度优先搜索遍历,并输出遍历的结点序列。(注:学号为奇数的同学使用邻接矩阵存储结构实现,学号为偶数的同学使用邻接表实现)提示:首先,根据用户输入的顶点总数和边数,构造无向图,然后以用户输入的顶点为起始点,进行深度优先、广度优先搜索遍历,并输出遍历的结果。三、 程序源代码:#include#include#include#define maxnum 20#define maxq 50typedef structchar *base;int front;int rear;Queue;typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data;ArcNode *firstarc;VNode,AdjListmaxnum;typedef structAdjList vertices;int vexnum,arcnum;int kind;ALGraph;int LocateVex(ALGraph *G,char v)int i;for(i=0;ivexnum;i+)if(G-verticesi.data=v)return i;void create(ALGraph *G)int i,j,k;char v1,v2;printf(输入结点及边的数目:n);scanf(%d%d,&G-vexnum,&G-arcnum);getchar();printf(输入总共结点的各信息:n);for(i=0;ivexnum;i+)scanf(%c,&G-verticesi.data);G-verticesi.firstarc=NULL;getchar();for(k=0;karcnum;k+)ArcNode *s,*q;printf(输入以v1为头v2为尾的两个结点:n);scanf(%c%c,&v1,&v2);getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);s=(ArcNode *)malloc(sizeof(ArcNode);q=(ArcNode *)malloc(sizeof(ArcNode);s-adjvex=j;s-nextarc=G-verticesi.firstarc;G-verticesi.firstarc=s;q-adjvex=i;q-nextarc=G-verticesj.firstarc;G-verticesj.firstarc=q;printf(该图的邻接表是:n);for(i=0;ivexnum;i+)ArcNode *p;printf(%3c,G-verticesi.data);p=G-verticesi.firstarc;while(p)printf(%3d,*p);p=p-nextarc;printf(n);void creat(Queue *q)q-base=(char *)malloc(maxq*sizeof(Queue);q-front=q-rear=0;int indui(Queue *q,char str)if(q-rear+1)%maxq=q-front)return 0;q-baseq-rear=str;q-rear=(q-rear+1)%maxq;return 1;int endui(Queue *q,char *str)if(q-rear=q-front)return 0;*str=q-baseq-front;q-front=(q-front+1)%maxq;return 1;int firstadj(ALGraph *G,char ch)int i,j,w;for(i=0;ivexnum;i+)if(G-verticesi.data=ch)j=i;if(G-verticesj.firstarc!=NULL)w=G-verticesj.firstarc-adjvex;return w;int nextadj(ALGraph *G,char ch,int w)int i,j;for(i=0;ivexnum;i+)if(G-verticesi.data=ch)j=i;ArcNode *p;p=G-verticesj.firstarc;while(p&(p-adjvex!=w)p=p-nextarc;if(p&p-nextarc)w=p-nextarc-adjvex;return w;elsew=-1;return w;void bianli(ALGraph *G,Queue *q)char u;int v,w;int visitedmaxnum=0,0,0,0,0;printf(以广度优先遍历图的各顶点的顺序是:n);for(v=0;vvexnum;v+)if(!visitedv)visitedv=1;printf(%3c,G-verticesv.data);indui(q,G-verticesv.data);while(q-rear!=q-front)endui(q,&u);for(w=firstadj(G,u);w=0;w=nextadj(G,u,w)if(!visitedw)visitedw=1;printf(%3c,G-verticesw.data);indui(q,G-verticesw.data);printf(n);void DFS(ALGraph *G,int v,int *visited)visitedv=1;printf(%3c,G-verticesv.data);for(int w=firstadj(G,G-verticesv.data);w=0;w=nextadj(G,G-verticesv.data,w)if(!visitedw)DFS(G,w,visited);void bianli2(ALGraph *G)printf(以深度优先遍历图的各顶点的顺序:n);int visited20;for(int v=0;vvexnum;v+)visitedv=0;for( v=0;vvexnum;v+)if(!visitedv)DFS(G,v,visited);printf(n);void main()ALGraph G;create(&G);Queue q;creat(&q);bianli2(&G);bianli(&G,&q);四、 测试结果:五、 小结通过此次实验让我对图的建立以及图的遍历有了一定的认识,但是还没有精通。过程中遇到了一系列的问题,例如:建队列后,进队列的是结点的信息,而刚开始我却让其所在数组的下标入队了,进而出错。该实验同时复习了链表,队列等。每一个实验过后通过总结可以知道自己的薄弱之处,从而下次注意,不再在同样的问题上花费不必要的时间。第 6 页 共 6 页
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号