数据结构和算法实验——图基本操作.doc

图的基本操作实验报告图的基本 图的基本操作 实验报告 实验名称 图的基本操作 实验目的 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表的存储结构； 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用； 掌握以邻接矩阵作为存储结构的生成图的最小生成树的普利姆算法； 实验内容 编制一个演示图的邻接表的创建、深度遍历、广度遍历操作的程序。 问题描述 用数据结构相关知识，实现邻接表的定义和操作。该程序包括图的邻接表的结点类型定义以及对图操作的具体的函数定义（包括：建立图的邻接表、深度优先遍历图、广度优先遍历图）。 问题分析 该实验是基于C语言和数据结构知识基础的对图的基本操作的检验，无需设计复杂的算法，程序语句也相对简单。因此，我直接按要求定义了对图操作的具体函数，并于主函数中实现对应的功能调用。 实验步骤 1．需求分析? ? ?本演示程序用VC++编写，完成图的邻接表的生成、遍历基本操作。? 输入的形式和输入值的范围：在输入邻接表顶点信息前，必须先确定该信息能正确创建邻接表。? ②? 输出的形式：在所有三种操作中都显示操作是否正确以及操作后图的内容。? ③? 程序所能达到的功能：完成图的邻接表的生成、深度优先遍历、广度优先遍历基本操作。? ④? 测试数据：创建操作中依次输入7,7作为顶点数和边数，以（0,1）（0,2）（1,3）（1,5）（3,4）（3,6）（4,5）作为各顶点信息生成一个邻接表。? 2．概要设计? ??1）为了实现上述程序功能，需要定义二叉树的抽象数据类型：??? ADT?Graph?{? ?数据对象：顶点的有穷非空集合和边的集合 数据关系：结点具有相同的数据类型及层次结构? 基本操作：? Void InitGraph(ALGraph *G) ???初始条件：无? ???操作结果：初始化图?? Void DFSTraverse(ALGraph *G)?? ???初始条件：图Graph已存在? ???操作结果：按深度优先遍历图的邻接表 Void BFSTraverse(ALGraph *G)?? ???初始条件：图Graph已存在? ???操作结果：按广度优先遍历图的邻接表 2）本程序包含7个函数：??? ①主函数main()?②?建立一个图的邻接表函数CreateGraphAL ()?③深度优先遍历图 DFS ()④广度优先遍历 BFS() 函数说明 #include stdio.h #include stdlib.h #define MaxVertexNum 100 #define QueueSize 30 typedef enum{FALSE,TRUE}Boolean; Boolean visited[MaxVertexNum]; typedef char VertexType; typedef int EdgeType; typedef struct node //边表结点 { int adjvex; //邻接点域 struct node *next; //域链 //若是要表示边上的权,则应增加一个数据域 }EdgeNode; typedef struct vnode //顶点边结点 { VertexType vertex; //顶点域 EdgeNode *firstedge;//边表头指针 }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型 typedef struct { AdjList adjlist; //邻接表 int n,e; //图中当前顶点数和边数 }ALGraph; void CreateGraphAL (ALGraph *G) { int i,j,k; EdgeNode * s; printf(请输入顶点数和边数(输入格式为:顶点数,边数)：\n); scanf(%d,%d,(G-n),(G-e)); // 读入顶点数和边数 printf(请输入顶点信息(输入格式为:顶点号CR)每个顶点以回车作为结束:\n); for (i=0;iG-n;i++) // 立有n个顶点的顶点表 { scanf(\n%c,(G-adjlist[i].vertex)); // 读入顶点信息 G-adjlist[i].firstedge=NULL; // 点的边表头指针设为空 }