图的遍历,利用邻接表.doc

华北水利水电学院 数据结构 实验报告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);四、 测试结果：五、 小结通过此次实验让我对图的建