无向图的连通分量和生成树

基本概念

无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，就能够访问图中所有顶点；
对于非连通图，则需要从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各连通分量中的顶点集。

设 E(G) 是连通图 G 中所有边的集合，则从图中任一顶点出发遍历时，必定将 E(G) 分成两个集合 T(G) 和 B(G)，其中 T(G) 是遍历图过程中经历的边的集合；B(G) 为剩余边的集合。
显然，T(G) 和图 G 中国所有顶点一起构成连通图 G 的极小连通子图，由深度优先搜索得到的称为深度优先生成树，由广度优先搜索得到的称为广度优先生成树。

对于非连通图，每个非连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成了非连通图的生成森林。

代码实现

深度优先生成树

使用（首）孩子兄弟表示法来存储生成树（森林），将新节点加入到生成树时需要区分首孩子和其他孩子节点。

容易看出，一棵生成树（一个连通分量）只有左孩子，没有右孩子。

// 深度优先生成树
// 从第 i 个顶点出发构建以 pre 为根的生成树
// 复用 pre 指向当前子树树根
void DFSTree(ALGraph *G, int i, int *visited, CSTNode *pre)
{
    // 以T为根的生成树，只有左子树，没有右子树
    int first = 1; // 用一个标志来标识第一个孩子节点
    CSTNode *e;
    ArcNode *p = G->vertices[i].firstarc;
    while(p)
    {
        if (0 == visited[p->adjvex])
        {
            visited[p->adjvex] = 1;
            // 分配新节点
            e = (CSTNode *)malloc(sizeof(CSTNode));
            e->data = G->vertices[p->adjvex].data;
            e->firstchild = NULL;
            e->nextsibling = NULL;
            // 添加到树中
            if (first)
            {
                pre->firstchild = e;
                first = 0;
            }
            else
            {
                pre->nextsibling = e;
            }
            // 记录上一个访问的节点，它是后一节点的兄弟或下一层的根
            pre = e;
            DFSTree(G, p->adjvex, visited, pre);
        }
        p = p->nextarc;
    }
}

深度优先生成森林

// 深度优先生成森林
void DFSForest(ALGraph *G, CSTree *T)
{
    int i, visited[MAX_VERTEX_NUM] = {0};
    // pre 记录上一棵生成树的根
    // e 生成树节点
    CSTNode *pre, *e;
    // 遍历
    for (i = 0; i < G->vexnum; ++i)
    {
        if (0 == visited[i])
        {
            visited[i] = 1;
            // 生成树根节点
            e = (CSTNode *)malloc(sizeof(CSTNode));
            e->data = G->vertices[i].data;
            e->firstchild = NULL;
            e->nextsibling = NULL;
            // 添加到树中
            if (*T)
                pre->nextsibling = e; // 当前生成树的根为上一生成树根的兄弟
            else
                (*T) = e; // 第一棵生成树的根
            pre = e; // 记下当前根，用于后续的生成树
            DFSTree(G, i, visited, pre);
        }
    }
}

广度优先生成树

// 广度优先生成树
// 从第 i 个顶点出发构建以 pre 为根的生成树i
// 复用 pre 指向当前子树树根
void BFSTree(ALGraph *G, int i, int *visited, CSTNode *pre)
{
    // 以T为根的生成树，只有左子树，没有右子树
    SqQueue Q; InitQueue(&Q);
    int first; // 用一个标志来标识第一个孩子节
    CSTNode *e;
    ArcNode *p;
    EnQueue(&Q, i);
    while(!QueueEmpty(&Q))
    {
        DeQueue(&Q, &i);
        p = G->vertices[i].firstarc;
        first = 1; // 用一个标志来标识第一个孩子节
        // 生成节点 i 的子树，第一个邻接点（用first来标识）存入firstchild，之后的邻接点存入 firstchild 的 nextsibling
        while(p)
        {
            if (0 == visited[p->adjvex])
            {
                visited[p->adjvex] = 1;
                // 分配新节点
                e = (CSTNode *)malloc(sizeof(CSTNode));
                e->data = G->vertices[p->adjvex].data;
                e->firstchild = NULL;
                e->nextsibling = NULL;
                // 添加到树中
                if (first)
                {
                    pre->firstchild = e;
                    first = 0;
                }
                else
                {
                    pre->nextsibling = e;
                }
                // 记录上一个访问的节点，它是后一节点的兄弟或下一层的根
                pre = e;
                // 将已生成的树节点入队，以便于之后构建它的子树
                EnQueue(&Q, p->adjvex);
            }
            p = p->nextarc;
        }
    }
}

广度优先生成森林

// 广度优先生成森林
void  BFSForest(ALGraph *G, CSTree *T)
{
    int i, visited[MAX_VERTEX_NUM] = {0};
    // pre 记录上一棵生成树的根
    // e 生成树节点
    CSTNode *pre, *e;
    // 遍历
    for (i = 0; i < G->vexnum; ++i)
    {
        if (0 == visited[i])
        {
            visited[i] = 1;
            e = (CSTNode *)malloc(sizeof(CSTNode)); // 生成树根节点
            e->data = G->vertices[i].data;
            e->firstchild = NULL;
            e->nextsibling = NULL;
            // 添加到树中
            if (*T)
                pre->nextsibling = e; // 当前生成树的根为上一生成树根的兄弟
            else
                (*T) = e; // 第一棵生成树的根
            pre = e; // 记下当前根，用于后续的生成树
            BFSTree(G, i, visited, pre);
        }
    }
}

完整代码可参见：GitHub

DONE！