数据结构——图的基本操作.doc

实验题目图的基本操作实1)掌握图的邻接矩阵、邻接表的表示方法。 2)掌握建立图的邻接矩阵的算法。 3)掌握建立图的邻接表的算法。 4)加深对图的理解，逐步培养解决实际问题的编程能力．需求分析 (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)调用上述函数实现下列操作。 ①建立一个图的邻接矩阵和图的邻接表。 ②采用递归深度优先遍历输出图的邻接矩阵 ③采用递归深度优先遍历输出图的邻接表。 ④采用图的广度优先调历输出图的邻接表。 ⑤采用图的广度优先遍历输出图的邻接矩阵．概要设计 ： //------------------------------- 邻接矩阵数据类型的定义-------------------------------- // 最大顶点个数 typedef struct { char vexs[MAX_VERTEX_NUM]; // 顶点向量 int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum,arcnum; // 图当前顶点数和弧数 }MGraph ; //--------------------------------邻接表数据类型的定义---------------------------------- typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 }ArcNode; typedef struct VNode { char data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; // 图当前顶点数和弧数 }LGraph; 本程序包含个函数： 主函数() 建立图的邻接矩阵，邻接表 Create_Graph () 邻接表表示的图的递归深度优先遍历 LDFS () 邻接矩阵表示的图的递归深度优先遍历 MDFS () 邻接表表示的图的广度优先遍历 LBFS () 邻接矩阵表示的图的广度优先遍历 MBFS（） 各函数间调用关系如下： 主函数的伪码 main() { ； ； } 5详细设计 //------------------------------- 邻接矩阵数据类型的定义-------------------------------- // 最大顶点个数 typedef struct { char vexs[MAX_VERTEX_NUM]; // 顶点向量 int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum,arcnum; // 图当前顶点数和弧数 }MGraph ; //--------------------------------邻接表数据类型的定义---------------------------------- typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 }ArcNode; typedef struct VNode { char data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; // 图当前顶点数和弧数