實验4创建一个图并输出图的深度优先和广度优先遍.doc

实 验 报 告 课程名称 数据结构 实验项目 创建一个图并输出图的深度优先和广度优先遍历结果 系 别___ _计算机学院 _ ______ 专 业___ ___ 班级/学号_ 学生姓名 __ ______ 实验日期 _ 成 绩 _______________________ 指导教师 实验题目：实验四------创建一个图并输出图的深度优先和广度优先遍历结果 实验目的 掌握图的存储结构； 掌握并实现图的深度优先和广度优先遍历算法； 理解图的应用，包括最小生成树、拓扑排序、关键路径、最短路径； 实验内容 以邻接矩阵或邻接表创建一个图，要求能够动态输入； 输出深度优先和广度优先遍历序列； 三选一应用题：1）两种算法构造最小生成树；2）有向无环图的拓扑排序和关键路径计算；3）两种算法计算最短路径。 设计与编码 程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、框图等来表示） 本实验用到的理论知识 图定义、图的两种存储结构的定义、算法，递归的深度优先遍历算法，广度优先遍历算法 （提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法） 具体算法设计 定义邻接矩阵的结构体类型 定义图的结构体类型 定义邻接表结构体类型、定义相关点和弧的相关信息 定义函数（将邻接矩阵转换为邻接表） 输出邻接表 将邻接表换为邻接矩阵 深度优先遍历、广度优先遍历 主函数 （提示：该部分主要是利用C、C++等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述） 编码 #includestdio.h #includemalloc.h #define max 100 typedef struct //以下定义临接矩阵类型 { int number; int info; }VertexType; typedef struct //图的定义 { int edges[max][max]; int n,e; VertexType vexs[max]; }MGraph; //定义邻接表类型 typedef struct ANode { int adjvex; struct ANode *nextarc; //指向下一条弧的指针 int info; //存放弧的信息（权值） }ArcNode; typedef struct Vnode { int data; ArcNode *firstarc; //指向第一条弧 }VNode; typedef VNode AdjList[max]; //AdjList是邻接表类型，把大表变成几个小的连接到一起 typedef struct { AdjList adjlist; int n,e; //图中顶点数和边数 }ALGraph; int visited[max]; //全局数组用于判断后面节点是否被访问过 void DispMat(MGraph g) //输出邻接矩阵 { int i,j; for(i=0;ig.n;i++) { for(j=0;jg.n;j++) if(g.edges[i][j]==0) printf(0 ); else printf(%d ,g.edges[i][j]); printf(\n); } } void MatToList(MGraph g,ALGraph *G) //将邻接矩阵g转换为邻接表G { int i,j; int n=g.n; ArcNode *p; G=(ALGraph *)malloc(sizeof(ALGraph)); for(i=0;in;i++) //给大的邻接表中所有头结点的指针域副初值 G-adjlist[i].firstarc=NULL; for(i=0;in;i++) //检查邻接矩阵的每个元素 for(j=0;jn;j++) if(g.edges[i][j]!=0) { p=(ArcNode *)malloc(sizeof(ArcNode));