作者：解学武

深度优先生成树和森林（C语言实现）

广度优先搜索（BFS）算法广度优先生成树和森林

我们知道，遍历连通图可以得到一棵生成树，遍历非连通图可以得到多棵生成树（又称生成森林）。

关于生成树和生成森林，读者可以猛击《生成树（森林）》做系统的了解。

所谓深度优先生成树，指的就是用深度优先搜索算法遍历连通图得到的生成树。同样的道理，用深度优先搜索算法遍历非连通图得到的生成森林又称深度优先生成森林。

那么，对于给定的一张（非）连通图，如何获得它对应的深度优先生成树（森林）呢？

深度优先生成树

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

//根据顶点数据，返回顶点在二维数组中的位置下标
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 CreadDFSTree(MGraph G, int v, CSTree* T) {
    int i, w;
    CSTree p = NULL, q = NULL;
    bool first = true;
    //将正在访问的该顶点的标志位设为true
    visited[v] = true;
    //依次遍历所有紧邻 v 的其它顶点
    for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
        //如果该临界点标志位为false，说明还未访问
        if (!visited[w]) {
            //用一个结点存储当前顶点
            p = (CSTree)malloc(sizeof(CSNode));
            p->data = G.vexs[w];
            p->lchild = NULL;
            p->nextsibling = NULL;
            //找到的第一个紧邻 v 的顶点作为它的左孩子结点，后续找到的顶点作为它左孩子的兄弟结点
            if (first) {
                (*T)->lchild = p;
                first = false;
            }
            //否则，为兄弟结点
            else {
                q->nextsibling = p;
            }
            q = p;
            //从当前访问的顶点出发，继续访问紧邻它且尚未访问的顶点
            CreadDFSTree(G, w, &q);
        }
    }
}

/*获得指定连通图 G 对应的深度优先生成树（二叉树）
* G：要遍历的连通图
* v: 从哪个顶点开始遍历，v 是该顶点在顶点数组中的位置下标
* T: 存储生成树
*/
void DFSTree(MGraph G, CSTree* T) {
    int v;
    CSTree p = NULL;
    //每个顶点的标记为初始化为false
    for (v = 0; v < G.vexnum; v++) {
        visited[v] = false;
    }
    //任选一个顶点，作为生成树的根结点
    p = (CSTree)malloc(sizeof(CSNode));
    p->data = G.vexs[0];
    p->lchild = NULL;
    p->nextsibling = NULL;
    (*T) = p;
    //从 vexs[0] 处顶点出发，构建生成树
    CreadDFSTree(G, 0, &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);//初始化图
    DFSTree(G, &T);
    //先序遍历二叉树
    PreOrderTraverse(T);
    DestroyBiTree(T);
    return 0;
}

程序中，DFSTree() 函数的功能是为构建生成树做准备工作，包括将所有顶点的标志域置为 flase，以及选择一个顶点，从该顶点开始遍历连通图。CreateDFSTree() 函数的功能是构建生成树，构建整棵树的过程采用了孩子兄弟表示法。

以图 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;

//根据顶点数据，返回顶点在二维数组中的位置下标
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 DFSTree(MGraph G, int v, CSTree* T) {
    int w;
    bool first = true;
    CSTree p = NULL, q = NULL;
    //将正在访问的该顶点的标志位设为true
    visited[v] = true;
    //依次遍历该顶点的所有邻接点
    for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
        //如果该临界点标志位为false，说明还未访问
        if (!visited[w]) {
            //为该邻接点初始化为结点
            p = (CSTree)malloc(sizeof(CSNode));
            p->data = G.vexs[w];
            p->lchild = NULL;
            p->nextsibling = NULL;
            //找到的第一个紧邻 v 的顶点作为它的左孩子结点，后续找到的顶点作为它左孩子的兄弟结点
            if (first) {
                (*T)->lchild = p;
                first = false;
            }
            //否则，为兄弟结点
            else {
                q->nextsibling = p;
            }
            q = p;
            //从当前顶点出发，继续访问紧邻它的顶点
            DFSTree(G, w, &q);
        }
    }
}

//构建深度优先生成森林，并转化为一整棵二叉树
void DFSForest(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;
            //以该结点为起始点，构建深度优先生成树
            DFSTree(G, v, &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() {
    CSTree T = NULL;
    MGraph G;//建立一个图的变量
    CreateDN(&G);//初始化图
    DFSForest(G, &T);
    //先序遍历二叉树
    PreOrderTraverse(T);
    DestroyBiTree(T);
    return 0;
}

程序中，DFSTree() 函数负责将各个连通分量转换为二叉树，DFSForest() 函数负责将生成森林转换为一整棵二叉树。

以图 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 11 12 3 6 4 5 7 8 10 9

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。

广度优先搜索（BFS）算法广度优先生成树和森林

加站长微信免费领
C语言学习小册加站长微信免费领C语言学习小册
微信ID：xiexuewu333