数据结构——图的基本操作VIP专享VIP免费

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 ) ⑤邻接矩阵表示的图的广度优先遍历 MBFS(MGraph g, int s, int n ) (2 )调用上述函数实现下列操作。 ①建立一个图的邻接矩阵和图的邻接表。 ②采用递归深度优先遍历输出图的邻接矩阵 ③采用递归深度优先遍历输出图的邻接表。 ④采用图的广度优先调历输出图的邻接表。 ⑤采用图的广度优先遍历输出图的邻接矩阵 4 ．概要设计 （1 ） ： /**********************************图的基本操作**********************************/ //------------------------------- 邻接矩阵数据类型的定义-------------------------------- // 最大顶点个数 typedef struct { char vexs[MAX_VERTEX_NUM]; // 顶点向量 int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum,arcnum; // 图当前顶点数和弧数 }MGraph ; //--------------------------------邻接表数据类型的定义---------------------------------- typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 福建师范大学物光院计算机教学辅导讲义 2 struct ArcNode *nextarc; // 指向下一条弧的指针 }ArcNode; typedef struct VNode { char data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; // 图当前顶点数和弧数 }LGraph; （2） 本程序主要包含 6 个函数：  主函数 main()  建立图的邻接矩阵，邻接表 Create_Graph ()  邻接表表示的图的递归深度优先遍历 LDFS ()  邻接矩阵表示的图的递归深度优先遍历 MDFS ()  邻接表表示的图的广度优先遍历 LBFS ()  邻接矩阵表示的图的广...