深度优先生成树和广度优先生成树（详解版）-百家乐凯发k8

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

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

图 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 (; ig.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  ) {
        for (int j=0; jvexnum; j  ) {
            g->arcs[i][j].adj=0;
        }
    }
    for (int i=0; iarcnum; i  ) {
        int v1,v2;
        scanf("%d,%d",&v1,&v2);
        int n=locatevex(*g, v1);
        int m=locatevex(*g, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        g->arcs[n][m].adj=1;
        g->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称
    }
}
int firstadjvex(mgraph g,int v)
{
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for(int i = 0; i=0; w=nextadjvex(g, v, w)) {
        //如果该临界点标志位为false，说明还未访问
        if (!visited[w]) {
            //为该邻接点初始化为结点
            cstree p=(cstree)malloc(sizeof(csnode));
            p->data=g.vexs[w];
            p->lchild=null;
            p->nextsibling=null;
            //该结点的第一个邻接点作为孩子结点，其它邻接点作为孩子结点的兄弟结点
            if (first) {
                (*t)->lchild=p;
                first=false;
            }
            //否则，为兄弟结点
            else{
                q->nextsibling=p;
            }
            q=p;
            //以当前访问的顶点为树根，继续访问其邻接点
            dfstree(g, w, &q);
        }
    }
}
//深度优先搜索生成森林并转化为二叉树
void dfsforest(mgraph g,cstree *t){
    (*t)=null;
    //每个顶点的标记为初始化为false
    for (int v=0; vdata=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;
}
int main() {
    mgraph g;//建立一个图的变量
    createdn(&g);//初始化图
    cstree t;
    dfsforest(g, &t);
    preordertraverse(t);
    return 0;
}

运行程序，拿图 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;//队列中存放的为树结点
    struct queue * next;
}queue;
//根据顶点本身数据，判断出顶点在二维数组中的位置
int locatevex(mgraph * g,vertextype v){
    int i=0;
    //遍历一维数组，找到变量v
    for (; ivexnum; 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));
    for (int i=0; ivexnum; i  ) {
        scanf("%d",&(g->vexs[i]));
    }
    for (int i=0; ivexnum; i  ) {
        for (int j=0; jvexnum; j  ) {
            g->arcs[i][j].adj=0;
            g->arcs[i][j].info=null;
        }
    }
    for (int i=0; iarcnum; i  ) {
        int v1,v2;
        scanf("%d,%d",&v1,&v2);
        int n=locatevex(g, v1);
        int m=locatevex(g, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        g->arcs[n][m].adj=1;
        g->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称
    }
}
int firstadjvex(mgraph g,int v)
{
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for(int i = 0; inext=null;
}
//结点v进队列
void enqueue(queue **q,cstree t){
    queue * element=(queue*)malloc(sizeof(queue));
    element->data=t;
    element->next=null;
   
    queue * temp=(*q);
    while (temp->next!=null) {
        temp=temp->next;
    }
    temp->next=element;
}
//队头元素出队列
void dequeue(queue **q,cstree *u){
    (*u)=(*q)->next->data;
    (*q)->next=(*q)->next->next;
}
//判断队列是否为空
bool queueempty(queue *q){
    if (q->next==null) {
        return true;
    }
    return false;
}
void bfstree(mgraph g,int v,cstree*t){
    cstree q=null;
    queue * q;
    initqueue(&q);
    //根结点入队
    enqueue(&q, (*t));
    //当队列为空时，证明遍历完成
    while (!queueempty(q)) {
        bool first=true;
        //队列首个结点出队
        dequeue(&q,&q);
        //判断结点中的数据在数组中的具体位置
        int v=locatevex(&g,q->data);
        //已经访问过的更改其标志位
        visited[v]=true;
        //遍历以出队结点为起始点的所有邻接点
        for (int 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;
            }
        }
    }
}
//广度优先搜索生成森林并转化为二叉树
void bfsforest(mgraph g,cstree *t){
    (*t)=null;
    //每个顶点的标记为初始化为false
    for (int v=0; vdata=g.vexs[v];
            p->lchild=null;
            p->nextsibling=null;
            //如果树未空，则该顶点作为树的树根
            if (!(*t)) {
                (*t)=p;
            }
            //该顶点作为树根的兄弟结点
            else{
                q->nextsibling=p;
            }
            //每次都要把q指针指向新的结点，为下次添加结点做铺垫
            q=p;
            //以该结点为起始点，构建广度优先生成树
            bfstree(g,v,&p);
        }
    }
}
//前序遍历二叉树
void preordertraverse(cstree t){
    if (t) {
        printf("%d ",t->data);
        preordertraverse(t->lchild);
        preordertraverse(t->nextsibling);
    }
    return;
}
int main() {
    mgraph g;//建立一个图的变量
    createdn(&g);//初始化图
    cstree t;
    bfsforest(g, &t);
    preordertraverse(t);
    return 0;
}

运行结果为：

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