数据结构实验报告图的遍历解析.doc

数据结构试验报告 实验四 图的存储及应用 实验题目：图的遍历问题 专业班级：计科系1405班 组 长：张纪远（座机电话号码18） 组 员：周振军（座机电话号码51） 朱新祥（座机电话号码52） 梁丽蓉（座机电话号码26） 段慧娟（座机电话号码12） 2016年月日实验报告 __综合设计__ 实验室_软件实验室三__ 实验题目 图的存储及应用 实验目的和要求 1．掌握图的存储思想及其存储实现 2．掌握图的深度、广度优先遍历算法思想及其程序实现 3．掌握图的常见应用算法的思想及其程序实现 需求分析 1．问题描述 使用菜单实现图的相关算法,如键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北，建立一个有向图或无向图（自定）的邻接表并输出该邻接表 ；在图的邻接表的基础上计算各顶点的度，并输出 ；以有向图的邻接表为基础实现输出它的拓扑排序序列 ；采用邻接表存储实现无向图的深度优先遍历；采用邻接表存储实现无向图的广度优先遍历；采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法 2.设计分析 调用菜单项，分别调用相应的子函数。注意顶点存储地名，使用字符数组来实现。 3.结构类型定义 typedef char vextype[10];/*顶点数据类型*/ typedef int edgetype;/*边数据类型*/ typedef struct vextype vex[MAXSIZE]; edgetype arc[MAXSIZE][MAXSIZE]; int vexnum,arcnum; Mgraph; typedef struct node int adjvex; struct node *next EdgeNode; typedef struct node vextype vex; EdgeNode * firstedge; VexNode; typedef struct VexNode adjvex[MAXSIZE]; int n,e; ALGraph; 概要设计 为了实现上述程序功能，#include #include #include typedef struct node //边表结点 int adj;//边表结点数据域 struct node *next; node; typedef struct vnode //顶点表结点 char name[20]; node *fnext; vnode,AList[20]; typedef struct AList List;//邻接表 int v,e;//顶点树和边数 *Graph; //建立无向邻接表 Graph CreatDG Graph G; int i,j,k; node *s; G malloc 20*sizeof vnode ; printf 请输入图的顶点数和边数 空格隔开 ： ; scanf %d%d,G- v,G- e ;//读入顶点数和边数 for i 0;i G- v;i++ printf 请输入图中第%d元素：,i+1 ; scanf %s,G- List[i].name ;//读入顶点信息 G- List[i].fnext NULL;//边表置为空表 for k 0;k G- e;k++ printf 请请输入第%d条边的两顶点序号 空格隔开 ：,k+1 ; scanf %d%d,i,j ;//读入边（Vi,Vj）的顶点对序号; s node * malloc sizeof node ;//生成边表结点 s- adj j; s- next G- List[i].fnext; G- List[i].fnext s;//将新结点*s插入顶点Vi的边表头部 s node * malloc sizeof node ; s- adj i;//邻接点序号为i s- next G- List[j].fnext; G- List[j].fnext s;// 将新结点*s插入顶点Vj的边表头部 return G; //有向邻接图 Graph CreatAG Graph G; int i,j,k; node *q; G malloc 20*sizeof vnode ; printf 请输入图的顶点数和边数【空格隔开】： ; scanf %d%d,G- v,G- e ; for i 0;i G- v;i++ printf 请输入图中第%d元素：,i+1 ; scanf %s,G- List[i].name ; //读入顶点信息 G- List[i].fnext NULL; for k 0;k G- e;