数据结构与算法实验图的

1、 数据结构与算法实验图的 基本操作 图的基本操实验报 图的基本操作实验报告 实验名称 图的基本操作 实验目的 1. 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表的存储结构； 2. 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用； 3. 掌握以邻接矩阵作为存储结构的生成图的最小生成树的普利姆算法； 实验内容 编制一个演示图的邻接表的创建、深度遍历、广度遍历操作的程序。 问题描述 用数据结构相关知识，实现邻接表的定义和操作。该程序包括图的邻接表的结点类型定义以及对图操作的具体的函数定义（包括：建立图的邻接表、深度优先遍历图、广度优先遍历图）

2、。 问题分析 该实验是基于C语言和数据结构知识基础的对图的基本操作的检验，无需设计复杂的算法，程序语句也相对简单。因此，我直接按要求定义了对图操作的具体函数，并于主函数中实现对应的功能调用。 实验步骤 1需求分析 本演示程序用VC+编写，完成图的邻接表的生成、遍历基本操作。 输入的形式和输入值的范围：在输入邻接表顶点信息前，必须先确定该信息能正确创建邻接表。 输出的形式：在所有三种操作中都显示操作是否正确以及操作后图的内 容。 程序所能达到的功能：完成图的邻接表的生成、深度优先遍历、广度优先遍历基本操作。 测试数据：创建操作中依次输入7,7作为顶点数和边数，以（0,1）（0,2）（1,3）（1

3、,5）（3,4）（3,6）（4,5）作为各顶点信息生成一个邻接表。 2概要设计 1）为了实现上述程序功能，需要定义二叉树的抽象数据类型：ADT Graph 数据对象：顶点的有穷非空集合和边的集合 数据关系：结点具有相同的数据类型及层次结构 基本操作： ALGraph *G) Void InitGraph( 初始条件：无 操作结果：初始化图 ALGraph *GVoid DFSTraverse() 初始条件：图Graph已存在 操作结果：按深度优先遍历图的邻接表 ALGraph *GVoid BFSTraverse( ) 初始条件：图Graph已存在 操作结果：按广度优先遍历图的邻接表 2）本程

4、序包含7个函数： CreateGraphAL 建立一个图的邻接表函数 main() 主函数 () 深度优先遍历图 DFS ()广度优先遍历 BFS() 函数说明 #include #include #define MaxVertexNum 100 #define QueueSize 30 typedef enumFALSE,TRUEBoolean; Boolean visitedMaxVertexNum; typedef char VertexType; typedef int EdgeType; typedef struct node /边表结点 int adjvex; /邻接点域 stru

5、ct node *next; /域链 /若是要表示边上的权,则应增加一个数据域 EdgeNode; typedef struct vnode /顶点边结点 VertexType vertex; /顶点域 EdgeNode *firstedge;/边表头指针 VertexNode; typedef VertexNode AdjListMaxVertexNum; /AdjList是邻接表类型 typedef struct AdjList adjlist; /邻接表 int n,e; /图中当前顶点数和边数 ALGraph; void CreateGraphAL (ALGraph *G) int i

6、,j,k; EdgeNode * s; ?牰湩晴尨请输入顶点数和边数(输入格式为:顶点数,边数)：n); scanf(%d,%d,&(G-n),&(G-e); / 读入顶点数和边数 ?牰湩晴尨请输入顶点信息(输入格式为:顶点号)每个顶点以回车作为结束:n); for (i=0;in;i+) / 立有n个顶点的顶点表 scanf(%c,&(G-adjlisti.vertex); / 读入顶点信息 G-adjlisti.firstedge=NULL; / 点的边表头指针设为空 ?牰湩晴尨请输入边的信息(输入格式为:i,j)：n); 建立边表 for (k=0;ke;k+) / scanf(%d,%

7、d,&i,&j); / 读入边的顶点对应序号 s=new EdgeNode; / 生成新边表结点s s-adjvex=j; / 邻接点序号为j s-next=G-adjlisti.firstedge; / 将新边表结点s插入到顶点Vi的边表头部 G-adjlisti.firstedge=s; s=new EdgeNode; s-adjvex=i; s-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /*/ /* 历遍先优度深*/ /*/ void DFS(ALGraph *G,int i) /以vi为出发点对邻接表表示的图G进行 深度优先搜

8、索 EdgeNode *p; printf(visit vertex:%cn,G-adjlisti.vertex); / 访问顶点vi visitedi=TRUE; /标记vi已访问 p=G-adjlisti.firstedge; /取vi边表的头指针 while(p) /依次搜索vi的邻接点vj，这里j=p-adjvex if (!visitedp-adjvex) /若vi尚未被访问 DFS(G,p-adjvex); /则以Vj为出发点向纵深搜索 p=p-next; /找vi的下一邻接点 void DFSTraverseM(ALGraph *G) int i; for(i=0;in;i+)

9、visitedi=FALSE; for(i=0;in;i+) if(!visitedi) DFS(G,i); /*/ /* 历遍先优度广*/ /*/ typedef struct int front; int rear; int count; int dataQueueSize; CirQueue; void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0; int QueueEmpty(CirQueue *Q) return Q-front=Q-rear; int QueueFull(CirQueue *Q) return (Q-rear

10、+1)%QueueSize=Q-front; void EnQueue(CirQueue *Q,int x) if (QueueFull(Q) printf(Queue overflow); else Q-count+; Q-dataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; int DeQueue(CirQueue *Q) int temp; if(QueueEmpty(Q) printf(Queue underflow); return false; else temp=Q-dataQ-front; Q-count-; Q-front=(Q-front+1

11、)%QueueSize; return temp; void BFS(ALGraph*G,int k) / 以vk为源点对用邻接表表示的图G进行广 度优先搜索 int i; CirQueue Q; /须将队列定义中DataType改为int EdgeNode *p; InitQueue(&Q); /队列初始化 printf(visit vertex:%cn,G-adjlistk.vertex); /访问源点vk visitedk=TRUE; EnQueue(&Q,k); /vk已访问，将其人队。（实际上是将其序号人队） while(!QueueEmpty(&Q) /队非空则执行 i=DeQue

12、ue(&Q); /相当于vi出队 p=G-adjlisti.firstedge; /取vi的边表头指针 while(p) /依次搜索vi的邻接点vj(令p-adjvex=j) if(!visitedp-adjvex) 未访问过vj若/ printf(visit vertex:%cn,G-adjlistp-adjvex.vertex); /访问vj visitedp-adjvex=TRUE; EnQueue(&Q,p-adjvex); /访问过的vj人队 p=p-next; /找vi的下一邻接点 void BFSTraverseM(ALGraph *G) int i; for (i=0;in;i

13、+) visitedi=FALSE; for (i=0;in;i+) if (!visitedi) BFS(G,i); /* */ /* 主函数调用 */ /*/ int main() int n; ALGraph G; CreateGraphAL(&G); 牰湩晴尨深度优先遍历：n); DFSTraverseM(&G); p楲瑮?广度优先遍历：n); BFSTraverseM(&G); return 0; 程序流程图 开始 访问V,置标志 求V邻接点 N 接邻有 开始 初始化 visitv N !IsEmpty结Y 对头元素出 调试报告 发现问题： 1. 在创建图的邻接表以后，得到的深度优先

14、遍历和自己在草稿纸上演算得到的序列不符。 2. 在创建图的邻接表以后，得到的广度优先遍历和自己在草稿纸上演算得到的序列不符。 调试： 1. 仔细检查程序后，发现是因为创建邻接表的方法是头插法； 2. 检查程序，发现依据队列的长度而判断队满和队空的条件不能实现。 解决方案： 1. 我重新在草稿纸上对用头插法建立的邻接表进行深度遍历； 2. 将队满的条件修改为：(rear+1)%QueueSize=front;将队空的条件修改为：rear=front 结果：结果运行正确！ 使用说明 建立邻接表 深度优先遍历 广度优先遍历 心得体会 数据结构顾名思义讲求的是一种存储结构，一路走来先后学习了表、树，最后学习的是图，对于每种存储结构学习之初都会学习一些基本操作，而操作之中又以创建和遍历为最基本的操作，只有熟练掌握了以后才能对其他操作进行研究和学习。 图的存储结构相比表和树都要复杂，其操作过程也较难进行掌握。仅仅是创建图的存储结构便分为矩阵、临接链表、十字链表等，对于每一种存储结构又分为有向与无向之分。然而，深度优先和广度优先是两种算法，其算法思想 并不依赖与元素的存储方式，也就是说算法思想不会因为存储结构的改变而