《数据结构—图的基本操作》由会员分享，可在线阅读，更多相关《数据结构—图的基本操作（11页珍藏版）》请在金锄头文库上搜索。
1、.1 实验题目图的基本操作2 实验目的1)掌握图的邻接矩阵、邻接表的表示方法。2)掌握建立图的邻接矩阵的算法。3)掌握建立图的邻接表的算法。4)加深对图的理解，逐步培养解决实际问题的编程能力3需求分析(1)编写图基本操作函数。建立图的邻接表，邻接矩阵Create_Graph( LGraph lg. MGraph mg ) 邻接表表示的图的递归深度优先遍历LDFS( LGraph g, int i )邻接矩阵表示的图的递归深度优先遍历MDFS( MGraph g,int i, int vn )邻接表表示的图的广度优先遍历LBFS( LGraph g, int s, int n )邻接矩阵表示的图
2、的广度优先遍历MBFS(MGraph g, int s, int n )(2)调用上述函数实现以下操作。建立一个图的邻接矩阵和图的邻接表。采用递归深度优先遍历输出图的邻接矩阵采用递归深度优先遍历输出图的邻接表。采用图的广度优先调历输出图的邻接表。采用图的广度优先遍历输出图的邻接矩阵4概要设计（1） ：/*图的基本操作*/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arum;/ 图当前顶点数和弧数MGr
3、aph ;/-邻接表数据类型的定义-typedef struct Arodeint adjvex;/ 该弧所指向的顶点的位置 struct Arode *nextarc;/ 指向下一条弧的指针 Arode;typedef struct VNodechar data;/ 顶点信息Arode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arum;/ 图当前顶点数和弧数 LGraph;（2） 本程序主要包含6个函数： 主函数main() 建立图的邻
4、接矩阵，邻接表Create_Graph() 邻接表表示的图的递归深度优先遍历LDFS() 邻接矩阵表示的图的递归深度优先遍历MDFS() 邻接表表示的图的广度优先遍历LBFS() 邻接矩阵表示的图的广度优先遍历MBFS各函数间调用关系如下：mainCreate_Graph ()LDFS ()MDFS ()LBFS ()MBFS（3） 主函数的伪码main() 定义邻接矩阵和邻接表；建立邻接矩阵和邻接表；邻接矩阵MDFS深度优先遍历；邻接矩阵MBFS广度优先遍历；邻接表LDFS深度优先遍历；邻接表LBFS广度优先遍历5详细设计/*图的基本操作*/- 邻接矩阵数据类型的定义-/ 最大顶点个数typ
5、edef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arum;/ 图当前顶点数和弧数MGraph ;/-邻接表数据类型的定义-typedef struct Arodeint adjvex;/ 该弧所指向的顶点的位置 struct Arode *nextarc;/ 指向下一条弧的指针 Arode;typedef struct VNodechar data;/ 顶点信息Arode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjList
6、MAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arum;/ 图当前顶点数和弧数 LGraph;int Create_Graph( MGraph *Mg , LGraph *Lg ) / 建立图的邻接矩阵，邻接表输入图的顶点个数字符，构造顶点向量输入图的任意两个顶点的弧构造邻接矩阵构造邻接表void LDFS(LGraph *Lg,int i) 邻接表表示的图的递归深度优先遍历显示顶点向量，指针指向下一个顶点向量下一个顶点没有被访问，继续否那么 退会上一个顶点向量的另一个边void MDFS(MGraph *Mg,int i)
7、邻接矩阵表示的图的递归深度优先遍历显示顶点向量，指针指向下一个顶点向量下一个顶点没有被访问，继续否那么 退会上一个顶点向量的另一个边void LBFS( LGraph *Lg )邻接表表示的图的广度优先遍历 初始化 visited初始化 队列没被访问过显示顶点向量入队出队访问下一个顶点向量void MBFS(MGraph *Mg )邻接矩阵表示的图的广度优先遍历初始化 visited初始化 队列没被访问过显示顶点向量入队出队访问下一个顶点向量/-主函数-main() 定义邻接矩阵和邻接表；建立邻接矩阵和邻接表；邻接矩阵MDFS深度优先遍历；邻接矩阵MBFS广度优先遍历；邻接表LDFS深度优先遍
8、历；邻接表LBFS广度优先遍历6测试结果7. 参考文献数据结构8附录#include #include #include #include #define OK 1#define ERROR 0#define MAX_VERTEX_NUM20/*图的基本操作*/int visitedMAX_VERTEX_NUM;/ 访问标志数组/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arum;/ 图当前顶点数和
9、弧数MGraph ;/-邻接表数据类型的定义-typedef struct Arodeint adjvex;/ 该弧所指向的顶点的位置 struct Arode *nextarc;/ 指向下一条弧的指针 Arode;typedef struct VNodechar data;/ 顶点信息Arode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arum;/ 图当前顶点数和弧数 LGraph;/_队列函数_typedef struct Queue
10、int arryMAX_VERTEX_NUM;int front,rear;Queue;Queue Q;void InitQueue()/ 队列初始化Q.front=Q.rear=0;int QueueEmpty(Queue *Q)/ 清空队列if(Q-front=Q-rear)return 1;elsereturn 0;void EnQueue(Queue *Q,int w)/ 入队if(Q-rear+1)%MAX_VERTEX_NUM=Q-front)printf(Error!);elseQ-arryQ-rear=w;Q-rear=(Q-rear+1)%MAX_VERTEX_NUM;int DeQueue(Queue *Q)/ 出队int u; if(Q-front=Q-rear)return -1;u=Q-front;Q-front=(Q-front+1)%MAX_VERTEX_NUM;return u;/_队列函数end_/*函数：Create_Graph*功能：建立图的邻接矩阵，邻接表
