广度优先搜索生成树怎么画_深度优先生成树和广度优先生成树（详解版）

前面已经给大家介绍了有关生成树和生成森林的有关知识，本节来解决对于给定的无向图，如何构建它们相对应的生成树或者生成森林。

其实在对无向图进行遍历的时候，遍历过程中所经历过的图中的顶点和边的组合，就是图的生成树或者生成森林。

图 1 无向图

例如，图 1 中的无向图是由 V1～V7 的顶点和编号分别为 a～i 的边组成。当使用深度优先搜索算法时，假设 V1 作为遍历的起始点，涉及到的顶点和边的遍历顺序为(不唯一)：

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

图 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]; //设置全局数组，记录标记顶点是否被访问过

typedef struct {

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

}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;

//根据顶点本身数据，判断出顶点在二维数组中的位置

int LocateVex(MGraph G,VertexType v){

int i=0;

//遍历一维数组，找到变量v

for (; i

if (G.vexs[i]==v) {

break;

}

}

//如果找不到，输出提示语句，返回-1

if (i>G.vexnum) {

printf("no such vertex.\n");

return -1;

}

return i;

}

//构造无向图

void CreateDN(MGraph *G){

scanf("%d,%d",&(G->vexnum),&(G->arcnum));

getchar();

for (int i=0; ivexnum; i++) {

scanf("%d",&(G->vexs[i]));

}

for (int i=0; ivexnum; i++) {