《数据结构实验报告无向图》由会员分享，可在线阅读，更多相关《数据结构实验报告无向图（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验题目: 无向图的建立与遍历实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。一、需求分析1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。2.该无向图以深度、广度优先遍历输出。3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束5.测试数据：abfdce顶点数和边数：6
2、,5顶点信息：a b c d e f边的顶点对应序号：0,10,20,32,43,4深度优先遍历输出：a d e c bf广度优先遍历输出：a d c b ef二 概要设计为了实现上述操作，应以邻接链表为存储结构。1.基本操作：void createalgraph(algraph &g) 创建无向图的邻接链表存储void dfstraverseal(algraph &g,int v)以深度优先遍历输出void bfstraverseal(algraph &g,int v)以广度优先遍历输出2.本程序包含四个模块：（1）主程序模块（2）无向图的邻接链表存储模块（3）深度优先遍历输出模块（4）广度
3、优先遍历输出模块3.模块调用图：主程序模块深度优先遍历输出模块广度优先遍历输出模块无向图的邻接链表存储模块三 详细设计1.元素类型，结点类型和指针类型：typedef struct nodeint adjvex;struct node *next;edgenode;typedef struct vnodechar vertex;edgenode *firstedge;vertxnode;typedef vertxnode Adjlistmaxvernum;typedef struct Adjlist adjlist;int n,e;algraph;edgenode *s;edgenode *s
4、tackmaxvernum,*p;2.每个模块的分析：（1）主程序模块int main()int v=0;algraph g;createalgraph(g);printf(以深度优先遍历输出n);dfstraverseal(g,v);printf(以广度优先遍历输出n);bfstraverseal(g,v);getchar();getchar();return 0;（2）无向图的邻接链表存储模块void createalgraph(algraph &g)int i,j,k;edgenode *s;printf(请输入顶点数和边数(输入格式为:顶点数,边数):n);scanf(%d,%d,&(
5、g.n),&(g.e); /*读入顶点数和边数*/getchar();printf(请输入顶点信息(输入格式为:(顶点号(CR):n);for(i=0;ig.n;i+) /*建立有n个顶点的顶点表*/scanf(%c,&(g.adjlisti.vertex); /*读入顶点信息*/getchar();g.adjlisti.firstedge=NULL; /*顶点的边表头指针设为空*/printf(请输入边的信息(输入格式为:i,j):n);for(k=0;kadjvex=j; /*邻接点序号为j*/s-next=g.adjlisti.firstedge; /*将新边表节点s插入到顶点vi的边表
6、头部*/g.adjlisti.firstedge=s; s=(edgenode *)malloc(sizeof(edgenode); /*生成新边表节点s*/s-adjvex=i; /*邻接点序号为i*/s-next=g.adjlistj.firstedge; /*将新边表节点s插入到顶点vj的边表头部*/g.adjlistj.firstedge=s;（3）深度优先遍历输出模块void dfstraverseal(algraph &g,int v)int j=0;edgenode *stackmaxvernum,*p;int visitedmaxvernum,top=-1,i;for(i=0;
7、i=0|p!=NULL)while(p!=NULL)if(visitedp-adjvex=1)p=p-next;elseprintf(%c ,g.adjlistp-adjvex.vertex); /*从v出发访问一个与v邻接的p所指的顶点*/j+;visitedp-adjvex=1; top+; stacktop=p; /*将p所指的顶点入栈*/ p=g.adjlistp-adjvex.firstedge; /*从p所指顶点出发*/if(top=0)p=stacktop; /*退栈，回溯查找已被访问节点的未被访问过的邻接点*/ top-; p=p-next;printf(n);（4）广度优先遍
8、历输出模块void bfstraverseal(algraph &g,int v)int i,front=-1,rear=-1,j=0;edgenode *p;for(i=0;iadjvex=0)visitedp-adjvex=1; printf(%c ,g.adjlistp-adjvex.vertex); j+; rear=rear+1; queuerear=p-adjvex;p=p-next;printf(n);3.函数调用图：int main()void dfstraverseal(algraph &g,int v)void bfstraverseal(algraph &g,int v)
9、void createalgraph(algraph &g)4.完整的程序：（见源文件）。四 使用说明、测试分析及结果1程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：请输入顶点数和边数(输入格式为:顶点数,边数):请输入顶点信息(输入格式为:(顶点号(CR):请输入边的信息(输入格式为:i,j):2.测试数据：abfdce顶点数和边数：6,5顶点信息：a b c d e f边的顶点对应序号：0,10,20,32,43,4深度优先遍历输出：a d e c bf广度优先遍历输出：a d c b ef3.运行界面：五、实验总结本次程序由于书上有相关程序作为参考，
10、所以编写起来比较顺手，通过本次编程，对于无向图的邻接链表存储有了一定的基础，同时还熟练掌握了无向图的深度、广度优先遍历输出，中间由于要存储无向不连通图，出了点小问题，在自己的努力下和同学的帮助下，完成了无向不连通图的存储与遍历输出。通过本次试验对于无向图有了更深的了解，可以很好地掌握它的建立与遍历输出。教师评语：#include#include#define maxvernum 100typedef struct nodeint adjvex;struct node *next;edgenode;typedef struct vnodechar vertex;edgenode *firstedge;vertxnode;typedef vertxnode Adjlistmaxvernum;typedef struct Adjlist adjlist;int n,e;algraph;int visitedmaxvernum;int queuemaxvernum;/创建无向图void createalgraph(algraph &g)int i,j,k;edgenode *s;printf(请输入顶点数和边数(输入格式为:顶点数,边数):n);scanf(%d,%d,&(g.n),&(g.e); /*读入顶点数和边数*/getchar();printf(请输入
