广度优先搜索生成树怎么画_深度优先生成树和广度优先生成树

本章的第一节中，介绍了有关

图 1 无向图

例如，图 1 中的无向图是由 V1～V7 的顶点和编号分别为 a～i 的边组成。当使用

此种遍历顺序构建的生成树为：

图 2 深度优先生成树

由深度优先搜索得到的树为深度优先生成树。同理，广度优先生成树，图 1 无向图以顶点 V1 为起始点进行广度优先搜索遍历得到的树，如图 3 所示：

图 3 广度优先生成树

非

非连通图在进行遍历时，实则是对非连通图中每个连通分量分别进行遍历，在遍历过程经过的每个顶点和边，就构成了每个连通分量的生成树。

非连通图中，多个连通分量构成的多个生成树为非连通图的生成森林。

深度优先生成森林

图 4 深度优先生成森林

例如，对图 4 中的非连通图 (a) 采用深度优先搜索算法遍历时，得到的深度优先生成森林(由 3 个深度优先生成树构成)如 (b) 所示(不唯一)。

非连通图在遍历生成森林时，可以采用

具体实现的代码：

#include

#include

#define MAX_VERtEX_NUM 20 //顶点的最大个数

#define VRType int //表示顶点之间的关系的变量类型

#define VertexType int //图中顶点的数据类型

typedef enum{false,true}bool; //定义bool型常量

bool visited[MAX_VERtEX_NUM]; //设置全局

运行程序，拿图 4(a)中的非连通图为例，构建的深度优先生成森林，使用孩子兄弟表示法表示为：

图5 孩子兄弟表示法表示深度优先生成森林

图中，3 种颜色的树各代表一棵深度优先生成树，使用孩子兄弟表示法表示，也就是将三棵树的树根相连，第一棵树的树根作为整棵树的树根。

运行结果

13,13

1

2

3

4

5

6

7

8

9

10

11

12

13

1,2

1,3

1,6

1,12

2,13

4,5

7,8

7,10

7,9

8,10

11,12

11,13

12,13

1 2 13 11 12 3 6 4 5 7 8 10 9

广度优先生成森林

非连通图采用广度优先搜索算法进行遍历时，经过的顶点以及边的集合为该图的广度优先生成森林。

拿图 4(a)中的非连通图为例，通过广度优先搜索得到的广度优先生成森林用孩子兄弟表示法为：

图6 广度优先生成森林(孩子兄弟表示法)

实现代码为：

#include

#include

#define MAX_VERtEX_NUM 20 //顶点的最大个数

#define VRType int //表示顶点之间的关系的变量类型

#define InfoType char //存储弧或者边额外信息的指针变量类型

#define VertexType int //图中顶点的数据类型

typedef enum{false,true}bool; //定义bool型常量

bool visited[MAX_VERtEX_NUM]; //设置全局数组，记录标记顶点是否被访问过

typedef struct {

VRType adj; //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。

InfoType * info; //弧或边额外含有的信息指针

}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {

VertexType vexs[MAX_VERtEX_NUM]; //存储图中顶点数据

AdjMatrix arcs; //二维数组，记录顶点之间的关系

int vexnum,arcnum; //记录图的顶点数和弧(边)数

}MGraph;

typedef struct CSNode{

VertexType data;

struct CSNode * lchild;//孩子结点

struct CSNode * nextsibling;//兄弟结点

}*CSTree,CSNode;

typedef struct Queue{

CSTree data;//

运行结果为：

13,13

1

2

3

4

5

6

7

8

9

10

11

12

13

1,2

1,3

1,6

1,12

2,13

4,5

7,8

7,10

7,9

8,10

11,12

11,13

12,13

1 2 13 3 6 12 11 4 5 7 8 9 10