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

- .

1．实验题目

图的根本操作

2．实验目的

1)掌握图的邻接矩阵、邻接表的表示方法。

2)掌握建立图的邻接矩阵的算法。

3)掌握建立图的邻接表的算法。

4)加深对图的理解，逐步培养解决实际问题的编程能力

⑤邻接矩阵表示的图的广度优先遍历MBFS(MGraph g, int s, int n )

(2)调用上述函数实现以下操作。

①建立一个图的邻接矩阵和图的邻接表。

②采用递归深度优先遍历输出图的邻接矩阵

③采用递归深度优先遍历输出图的邻接表。

④采用图的广度优先调历输出图的邻接表。

⑤采用图的广度优先遍历输出图的邻接矩阵

4．概要设计

（1） ：

/**********************************图的根本操作**********************************/

int vexnum,arum; // 图当前顶点数和弧数

}MGraph ;

//--------------------------------邻接表数据类型的定义----------------------------------

typedef struct Arode

{

. -可修遍-

- -

int adjvex; // 该弧所指向的顶点的位置

struct Arode *nextarc; // 指向下一条弧的指针

}Arode;

{

AdjList vertices;

int vexnum,arum; // 图当前顶点数和弧数

}LGraph;

（2） 本程序主要包含 6 个函数：

 主函数 main()

 建立图的邻接矩阵，邻接表 Create_Graph()

 邻接表表示的图的递归深度优先遍历 LDFS()

 邻接矩阵表示的图的递归深度优先遍历 MDFS()

 邻接表表示的图的广度优先遍历 LBFS()

邻接矩阵 MDFS 深度优先遍历；

邻接矩阵 MBFS 广度优先遍历 ；

邻接表 LDFS 深度优先遍历；

邻接表 LBFS 广度优先遍历

}

- -

5 详细设计

{

char vexs[MAX_VERTEX_NUM]; // 顶点向量

int acrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵

int vexnum,arum; // 图当前顶点数和弧数

//--------------------------------邻接表数据类型的定义----------------------------------

typedef struct Arode

{

int adjvex; // 该弧所指向的顶点的位置

struct Arode *nextarc; // 指向下一条弧的指针

}Arode;

{

AdjList vertices;

int vexnum,arum; // 图当前顶点数和弧数

}LGraph;

int Create_Graph( MGraph *Mg , LGraph *Lg ) // 建立图的邻接矩阵，邻接表

{

输入图的顶点个数〔字符〕，构造顶点向量

输入图的任意两个顶点的弧

构造邻接矩阵

构造邻接表

否那么 退会上一个顶点向量的另一个边

}

void MDFS(MGraph *Mg,int i)邻接矩阵表示的图的递归深度优先遍历

{

显示顶点向量，