图的遍历,利用邻接表

《图的遍历,利用邻接表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、华北水利水电学院数据结构实验报告2012～2013学年第二学期2012级（专升本）计算机科学与技术专业班级：196学号：201219614姓名：吕竹青实验四图的应用一、实验题目：图的应用——深度优先／广度优先搜索遍历二、实验内容：很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。要求：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。（注：学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接表实现）提示：首先，根据用户输入的顶点总数和

2、边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。三、程序源代码：#include#include#include#definemaxnum20#definemaxq50typedefstruct{char*base;intfront;intrear;}Queue;typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{chardata;第6页共6页ArcNode*

3、firstarc;}VNode,AdjList[maxnum];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;intLocateVex(ALGraph*G,charv){inti;for(i=0;ivexnum;i++)if(G->vertices[i].data==v)returni;}voidcreate(ALGraph*G){inti,j,k;charv1,v2;printf("输入结点及边的数目：");scanf("%d%d",&G->vexnum,&G->arcnum);

4、getchar();printf("输入总共结点的各信息：");for(i=0;ivexnum;i++){scanf("%c",&G->vertices[i].data);G->vertices[i].firstarc=NULL;}getchar();for(k=0;karcnum;k++){ArcNode*s,*q;printf("输入以v1为头v2为尾的两个结点：");scanf("%c%c",&v1,&v2);getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);第6页共6页s=(ArcNode*)mall

5、oc(sizeof(ArcNode));q=(ArcNode*)malloc(sizeof(ArcNode));s->adjvex=j;s->nextarc=G->vertices[i].firstarc;G->vertices[i].firstarc=s;q->adjvex=i;q->nextarc=G->vertices[j].firstarc;G->vertices[j].firstarc=q;}printf("该图的邻接表是：");for(i=0;ivexnum;i++){ArcNode*p;printf("%3c",G->vertices[i].dat

6、a);p=G->vertices[i].firstarc;while(p){printf("%3d",*p);p=p->nextarc;}printf("");}}voidcreat(Queue*q){q->base=(char*)malloc(maxq*sizeof(Queue));q->front=q->rear=0;}intindui(Queue*q,charstr){if((q->rear+1)%maxq==q->front)return0;q->base[q->rear]=str;q->rear=(q->rear+1)%maxq;return1;}intend

7、ui(Queue*q,char*str){if(q->rear==q->front)return0;*str=q->base[q->front];第6页共6页q->front=(q->front+1)%maxq;return1;}intfirstadj(ALGraph*G,charch){inti,j,w;for(i=0;ivexnum;i++)if(G->vertices[i].data==ch)j=i;if(G->vertices[j].firstarc!=NULL)w=G->vertices[j].f