作者：解学武
广度优先生成树和森林（C语言实现）
我们知道，遍历连通图可以得到一棵生成树，遍历非连通图可以得到多棵生成树（又称生成森林）。
那么，对于给定的一张（非）连通图，如何获得它对应的广度优先生成树（森林）呢？
图 1 连通图和它对应的广度优先生成树
图 2 广度优先生成树不是二叉树
和普通树相比，二叉树更容易存储，操作起来也更简单，比如二叉树有现成的四种遍历算法。实际场景中，我们通常先借助孩子兄弟表示法将普通树转换为二叉树，然后再操作二叉树实现自己想要的功能。
对于给定的一张连通图，如果我们想获得它对应的一棵广度优先生成树，并且还是经过孩子兄弟表示法转换后的二叉树，该如何编码实现呢？这里给大家提供一种实现思路：
以图 1a) 的连通图为例，程序最终构建出的广度优先生成树为：
图 3 程序构建的广度优先生成树
程序的执行结果为：
图 4 非连通图和它的连通分量
对图 4a) 进行广度优先搜索，其本质是依次遍历 3 个连通分量，最终得到 3 棵生成树，如下图所示
图 5 广度优先生成森林
借助孩子兄弟表示法，可以将森林中的每一棵生成树都转换为二叉树，然后再将多棵二叉树合并为一整颗二叉树。比如将图 5 的生成森林转换为一整棵二叉树，如下图所示：
图 6 生成森林转换为一整棵二叉树
对于给定的一张非连通图，如果我们想获得它对应的广度优先生成森林，并且是经过孩子兄弟表示法转换后的一整棵二叉树，该如何编码实现呢？这里给大家提供一种实现思路：
以图 4a) 中的非连通图为例，程序最终构建的广度优先生成树如图 6c) 所示，程序的执行结果为：
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。
所谓广度优先生成树，指的就是用广度优先搜索算法遍历连通图得到的生成树。同样的道理，用广度优先搜索算法遍历非连通图得到的生成森林又称广度优先生成森林。关于生成树和生成森林，读者可以猛击《生成树（森林）》做系统的了解。
那么，对于给定的一张（非）连通图，如何获得它对应的广度优先生成树（森林）呢？
广度优先生成树
图 1a) 是一个连通图，用广度优先搜索算法遍历它，得到的广度优先生成树如图 1b) 所示：图 1 连通图和它对应的广度优先生成树
注意，对连通图进行广度优先搜索，得到的生成树往往是一棵普通树，而非二叉树，例如：图 1a) 对应的广度优先生成树有很多棵，图 1b) 只是其中的一棵。
图 2 广度优先生成树不是二叉树
和普通树相比，二叉树更容易存储，操作起来也更简单，比如二叉树有现成的四种遍历算法。实际场景中，我们通常先借助孩子兄弟表示法将普通树转换为二叉树，然后再操作二叉树实现自己想要的功能。
对于给定的一张连通图，如果我们想获得它对应的一棵广度优先生成树，并且还是经过孩子兄弟表示法转换后的二叉树，该如何编码实现呢？这里给大家提供一种实现思路：
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERtEX_NUM 20 //顶点的最大数量
#define VRType int //表示顶点之间关系的数据类型
#define VertexType int //图中顶点的数据类型
#define States 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;
typedef struct Queue {
CSTree data;//队列中存放的为树结点
struct Queue* next;
}Queue;
//根据顶点数据，返回顶点在二维数组中的位置下标
int LocateVex(MGraph* G, VertexType v) {
int i = 0;
//遍历一维数组，找到变量v
for (; i < G->vexnum; i++) {
if (G->vexs[i] == v) {
break;
}
}
//如果找不到，输出提示语句，返回-1
if (i > G->vexnum) {
printf("no such vertex.\n");
return -1;
}
return i;
}
//构造无向图
States CreateDN(MGraph* G) {
int i, j, n, m;
int v1, v2;
scanf("%d,%d", &(G->vexnum), &(G->arcnum));
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &(G->vexs[i]));
}
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
G->arcs[i][j].adj = 0;
}
}
for (i = 0; i < G->arcnum; i++) {
scanf("%d,%d", &v1, &v2);
n = LocateVex(G, v1);
m = LocateVex(G, v2);
if (m == -1 || n == -1) {
printf("no this vertex\n");
return -1;
}
G->arcs[n][m].adj = 1;
G->arcs[m][n].adj = 1;//无向图的二阶矩阵沿主对角线对称
}
return 1;
}
int FirstAdjVex(MGraph G, int v)
{
int i;
//对于数组下标 v 处的顶点，找到第一个和它相邻的顶点，并返回该顶点的数组下标
for (i = 0; i < G.vexnum; i++) {
if (G.arcs[v][i].adj) {
return i;
}
}
return -1;
}
int NextAdjVex(MGraph G, int v, int w)
{
int i;
//对于数组下标 v 处的顶点，从 w 位置开始继续查找和它相邻的顶点，并返回该顶点的数组下标
for (i = w + 1; i < G.vexnum; i++) {
if (G.arcs[v][i].adj) {
return i;
}
}
return -1;
}
//初始化队列
void InitQueue(Queue** Q) {
(*Q) = (Queue*)malloc(sizeof(Queue));
(*Q)->next = NULL;
}
//结点T进队列
void EnQueue(Queue** Q, CSTree T) {
Queue* temp = (*Q);
Queue* element = (Queue*)malloc(sizeof(Queue));
element->data = T;
element->next = NULL;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = element;
}
//队头元素出队列
void DeQueue(Queue** Q, CSTree* u) {
Queue* del = (*Q)->next;
(*u) = (*Q)->next->data;
(*Q)->next = (*Q)->next->next;
free(del);
}
//判断队列是否为空
bool QueueEmpty(Queue* Q) {
if (Q->next == NULL) {
return true;
}
return false;
}
//释放队列占用的堆空间
void DelQueue(Queue* Q) {
Queue* del = NULL;
while (Q->next) {
del = Q->next;
Q->next = Q->next->next;
free(del);
}
free(Q);
}
//构建广度优先生成树
void CreateBFSTree(MGraph G, CSTree* T) {
int v, w;
CSTree q = NULL;
Queue* Q = NULL;
InitQueue(&Q);
//根结点入队
EnQueue(&Q, (*T));
//当队列为空时，证明遍历完成
while (!QueueEmpty(Q)) {
bool first = true;
//队列首个结点出队
DeQueue(&Q, &q);
//判断结点中的数据在数组中的具体位置
v = LocateVex(&G, q->data);
//已经访问过的更改其标志位
visited[v] = true;
//将所有和 v 紧邻的其它结点入队
for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
//标志位为false，证明未遍历过
if (!visited[w]) {
//新建一个结点 p，存放当前遍历的顶点
CSTree p = (CSTree)malloc(sizeof(CSNode));
p->data = G.vexs[w];
p->lchild = NULL;
p->nextsibling = NULL;
//当前结点入队
EnQueue(&Q, p);
//更改标志位
visited[w] = true;
//如果是出队顶点的第一个邻接点，设置p结点为其左孩子
if (first) {
q->lchild = p;
first = false;
}
//否则设置其为兄弟结点
else {
q->nextsibling = p;
}
q = p;
}
}
}
DelQueue(Q);
}
void BFSTree(MGraph G, CSTree* T) {
int v;
//每个顶点的标记为初始化为false
for (v = 0; v < G.vexnum; v++) {
visited[v] = false;
}
//将下标为 0 的顶点作为树的根结点
(*T) = (CSTree)malloc(sizeof(CSNode));
(*T)->data = G.vexs[0];
(*T)->lchild = NULL;
(*T)->nextsibling = NULL;
//构建广度优先生成树
CreateBFSTree(G, T);
}
//前序遍历二叉树
void PreOrderTraverse(CSTree T) {
if (T) {
printf("%d ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->nextsibling);
}
return;
}
//后序遍历二叉树，释放树占用的内存
void DestroyBiTree(CSTree T) {
if (T) {
DestroyBiTree(T->lchild);//销毁左孩子
DestroyBiTree(T->nextsibling);//销毁右孩子
free(T);//释放结点占用的内存
}
}
int main() {
MGraph G;//建立一个图的变量
CSTree T = NULL;
CreateDN(&G);//初始化图
BFSTree(G, &T);
PreOrderTraverse(T);
DestroyBiTree(T);
return 0;
}
程序中，BFSTree() 函数的功能是为构建生成树做准备工作，包括将所有顶点的标志域置为 flase，以及选择一个顶点，从该顶点开始遍历连通图。CreateBFSTree() 函数的功能是构建生成树，构建整棵树的过程采用了孩子兄弟表示法。以图 1a) 的连通图为例，程序最终构建出的广度优先生成树为：
图 3 程序构建的广度优先生成树
程序的执行结果为：
8,9
1
2
3
4
5
6
7
8
1,2
2,4
2,5
4,8
5,8
1,3
3,6
6,7
7,3
1 2 4 8 5 3 6 7
广度优先生成森林
图 4a) 是一张非连通图，它可以分为图 4b) 所示的 3 个连通分量：图 4 非连通图和它的连通分量
对图 4a) 进行广度优先搜索，其本质是依次遍历 3 个连通分量，最终得到 3 棵生成树，如下图所示
图 5 广度优先生成森林
借助孩子兄弟表示法，可以将森林中的每一棵生成树都转换为二叉树，然后再将多棵二叉树合并为一整颗二叉树。比如将图 5 的生成森林转换为一整棵二叉树，如下图所示：
图 6 生成森林转换为一整棵二叉树
对于给定的一张非连通图，如果我们想获得它对应的广度优先生成森林，并且是经过孩子兄弟表示法转换后的一整棵二叉树，该如何编码实现呢？这里给大家提供一种实现思路：
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERtEX_NUM 20 //顶点的最大数量
#define VRType int //表示顶点之间关系的数据类型
#define VertexType int //图中顶点的数据类型
#define States 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;
typedef struct Queue {
CSTree data;//队列中存放的为树结点
struct Queue* next;
}Queue;
//根据顶点数据，返回顶点在二维数组中的位置下标
int LocateVex(MGraph* G, VertexType v) {
int i = 0;
//遍历一维数组，找到变量v
for (; i < G->vexnum; i++) {
if (G->vexs[i] == v) {
break;
}
}
//如果找不到，输出提示语句，返回-1
if (i > G->vexnum) {
printf("no such vertex.\n");
return -1;
}
return i;
}
//构造无向图
States CreateDN(MGraph* G) {
int i, j, n, m;
int v1, v2;
scanf("%d,%d", &(G->vexnum), &(G->arcnum));
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &(G->vexs[i]));
}
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
G->arcs[i][j].adj = 0;
}
}
for (i = 0; i < G->arcnum; i++) {
scanf("%d,%d", &v1, &v2);
n = LocateVex(G, v1);
m = LocateVex(G, v2);
if (m == -1 || n == -1) {
printf("no this vertex\n");
return -1;
}
G->arcs[n][m].adj = 1;
G->arcs[m][n].adj = 1;//无向图的二阶矩阵沿主对角线对称
}
return 1;
}
int FirstAdjVex(MGraph G, int v)
{
int i;
//对于数组下标 v 处的顶点，找到第一个和它相邻的顶点，并返回该顶点的数组下标
for (i = 0; i < G.vexnum; i++) {
if (G.arcs[v][i].adj) {
return i;
}
}
return -1;
}
int NextAdjVex(MGraph G, int v, int w)
{
int i;
//对于数组下标 v 处的顶点，从 w 位置开始继续查找和它相邻的顶点，并返回该顶点的数组下标
for (i = w + 1; i < G.vexnum; i++) {
if (G.arcs[v][i].adj) {
return i;
}
}
return -1;
}
//初始化队列
void InitQueue(Queue** Q) {
(*Q) = (Queue*)malloc(sizeof(Queue));
(*Q)->next = NULL;
}
//结点T进队列
void EnQueue(Queue** Q, CSTree T) {
Queue* temp = (*Q);
Queue* element = (Queue*)malloc(sizeof(Queue));
element->data = T;
element->next = NULL;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = element;
}
//队头元素出队列
void DeQueue(Queue** Q, CSTree* u) {
Queue* del = (*Q)->next;
(*u) = (*Q)->next->data;
(*Q)->next = (*Q)->next->next;
free(del);
}
//判断队列是否为空
bool QueueEmpty(Queue* Q) {
if (Q->next == NULL) {
return true;
}
return false;
}
//释放队列占用的堆空间
void DelQueue(Queue* Q) {
Queue* del = NULL;
while (Q->next) {
del = Q->next;
Q->next = Q->next->next;
free(del);
}
free(Q);
}
//构建广度优先生成树
void BFSTree(MGraph G, CSTree* T) {
int v, w;
CSTree q = NULL, p = NULL;
Queue* Q = NULL;
InitQueue(&Q);
//根结点入队
EnQueue(&Q, (*T));
//当队列为空时，证明遍历完成
while (!QueueEmpty(Q)) {
bool first = true;
//队列首个结点出队
DeQueue(&Q, &q);
//判断结点中的数据在数组中的具体位置
v = LocateVex(&G, q->data);
//已经访问过的更改其标志位
visited[v] = true;
//将紧邻 v 的其它结点全部入队，并以孩子兄弟表示法构建生成树
for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
//标志位为false，证明未遍历过
if (!visited[w]) {
//新建一个结点 p，存放当前遍历的顶点
p = (CSTree)malloc(sizeof(CSNode));
p->data = G.vexs[w];
p->lchild = NULL;
p->nextsibling = NULL;
//当前结点入队
EnQueue(&Q, p);
//更改标志位
visited[w] = true;
//出队的第一个顶点，设置为 q 的左孩子
if (first) {
q->lchild = p;
first = false;
}
//否则设置其为兄弟结点
else {
q->nextsibling = p;
}
q = p;
}
}
}
DelQueue(Q);
}
//广度优先搜索生成森林并转化为二叉树
void BFSForest(MGraph G, CSTree* T) {
int v;
CSTree q = NULL, p = NULL;
//每个顶点的标记为初始化为false
for (v = 0; v < G.vexnum; v++) {
visited[v] = false;
}
//遍历图中所有的顶点
for (v = 0; v < G.vexnum; v++) {
//如果该顶点的标记位为false，证明未访问过
if (!(visited[v])) {
//新建一个结点，表示该顶点
p = (CSTree)malloc(sizeof(CSNode));
p->data = G.vexs[v];
p->lchild = NULL;
p->nextsibling = NULL;
//如果树未空，则该顶点作为树的树根
if (!(*T)) {
(*T) = p;
}
//该顶点作为树根的兄弟结点
else {
q->nextsibling = p;
}
//每次都要把q指针指向新的结点，为下次添加结点做铺垫
q = p;
//以该结点为起始点，构建广度优先生成树
BFSTree(G,&p);
}
}
}
//前序遍历二叉树
void PreOrderTraverse(CSTree T) {
if (T) {
printf("%d ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->nextsibling);
}
return;
}
//后序遍历二叉树，释放树占用的内存
void DestroyBiTree(CSTree T) {
if (T) {
DestroyBiTree(T->lchild);//销毁左孩子
DestroyBiTree(T->nextsibling);//销毁右孩子
free(T);//释放结点占用的内存
}
}
int main() {
MGraph G;//建立一个图的变量
CSTree T = NULL;
CreateDN(&G);//初始化图
BFSForest(G, &T);
PreOrderTraverse(T);
DestroyBiTree(T);
return 0;
}
程序中，BFSTree() 函数负责生成各个连通分量对应的二叉树，BFSForest() 函数负责将多个二叉树整合为一整棵二叉树。以图 4a) 中的非连通图为例，程序最终构建的广度优先生成树如图 6c) 所示，程序的执行结果为：
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
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。
ICP备案：