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

1

．实验题目

图的基本操作

2

．实验目的

1)

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

2)

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

3)

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

< /p>

4)

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

3

．需求分析

(1)

编写图基本操作函数。

①建立图的邻接表，邻接矩阵

Create_Graph( LGraph lg. MGraph mg )

②邻接表表示的图的递归深度优先遍历

LDFS( LGraph g, int i )

③邻接矩阵表示的图的递归深度优先遍历

MDFS( MGraph g,int i, int vn )

④邻接表表示的图的广度优先遍历

⑤邻接矩阵表示的图的广度优先遍历

(2)

调用上述函数实现下列操作。

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

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

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

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

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

4

．概要设计

（

1

）

：

/************** ********************

图的基本操作

** ********************************/

//-------------------------------

---------------------- ----------

//

最大顶点个数

LBFS( LGraph g, int s, int n )

MBFS(MGraph g, int s, int n )

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;

2

）

本程序 主要包含

6

个函数：

?

主函数

main()

?

建立图的邻接矩阵，邻接表

?

邻接表表示的图的递归深度优先遍历

?

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

?

邻接表表示的图的广度优先遍历

?

邻接矩阵表示的图的广度优先遍历

各函数间调用关系如下：

main

3

）

主函数的伪码

main()

{

定义邻接矩阵和邻接表；

建立邻接矩阵和邻接表；

邻接矩阵

MDFS

< br>深度优先遍历；

邻接矩阵< /p>

MBFS

广度优先遍历

；

邻接表

LDFS

深度优先遍历；

LBFS

广度优先遍历

福建师范大学物光院计算机教学辅导讲义

//

指向下一条弧的指针

//

顶点信息

//

指向第一条依附该顶点的弧的指针

//

图当前顶点数和弧数

Create_Graph

()

LDFS

()

MDFS

()

LBFS

()

MBFS

（）

Create_Graph

()

LDFS

()

MDFS

()

LBFS

()

MBFS

（）

2

（

（

福建师范大学物光院计算机教学辅导讲义

}

5

详细设计

/**********************************

图的基本 操作

**********************************/

//-------------------------------