04月
02

发表于 • 字数统计 5776 • 被 1,111 人看爆

图的生成树

对于具有n个顶点的连通图，包含了该图的全部n个顶点，仅包含它的n-1条边的一个极小连通子图(边最少)被称为生成树。
一个图的生成树为一个无回路的连通图。也就是说，若在图中任意添加一条边，就会出现回路﹔若在图中去掉任何一条边，都会使之成为非连通图。
一个连通图的生成树不一定是唯一的。

一颗具有n个顶点的生成树有仅有n-1条边，但有n-1条边的图不一定是生成树。同一个图可以有不同的生成树

例1

下图中图(b)和(c)是图(a)的生成树。
图生成树示例1.png

例2

下图中图(b)和图(c)都是图(a)的生成树
图生成树示例2.png

由深度优先搜索所得的生成树称为深度优先生成树，简称为DFS生成树
由广度优先搜索所得的生成树称之为广度优先生成树，简称为BFS生成树。

例3

下图中图(b)是图(a)从V0开始的深度优先搜索所得的生成树，图(c)是图(a)从V0开始的广度优先搜索的生成树。
从V0开始的深度优先搜索序列:V0，V1，V2，V5，V4，V6，V3，V7，V8。
从V0开始的广度优先搜索序列:V0，V1，V3，V4，V2，V6，V8，V5，V7。

广深优先搜索生成树示例.png

最小生成树

对于连通的带权图(网)G，其生成树也是带权的。把生成树各边的权值总和称为该树的权，把权值最小的生成树称为图的最小生成树(Mininum Sparning Tree，MST)。

例

图(b)、 (c)、 (d)是图(a)的三棵生成树。
最小生成树示例.png

MST性质

假设N=(V, {E})是一个连通网，U是顶点集V得一个非空子集，若(u, v)是一条具有最小权值的边，其中u∈U，v∈V - U，则必存在一颗包含边(u, v)的最小生成树

证明

用反证法，假设连通网N的任何一颗最小生成树都不包含边(u, v)，设T是连通网上的一颗最小生成树，当把边(u, v)加入到T中，有生成树的定义知，T中必存在一条包含(u, v)的回路。而另一方面，由于T是生成树，则T上必存在另一条边(u', v')，其中u'∈U，v'∈V-U，且u和u'之间、v和v'之间均有路径相通。删去边(u', v')，便可消除上述回路，同时得到另一颗包含边(u, v)生成树T'。因为(u, v)的代价不大于(u', v')的代价，所以T'的代价也不大于T的代价。这与假设矛盾，因此命题成立

多数算法利用MST性质，常用的算法只有：普利姆算法和克鲁斯卡尔算法

1.普里姆(Prim)算法

算法思想

  用自然语言描述的Prim算法:设G= (V,G)为具有n个顶点的带权连通图，T=(U，TE)为G的一个最小生成树(子图)，其中U是T的顶点集，TE是T的边集，U和TE的初值为空。

  算法开始时，首先从V中任取一个顶点(假定取v1)，将它并入U中，此时U=。然后只要U是V的真子集(即U⊂V)，就从那些一个端点已在T中，另一个端点仍在T外的所有边中，找到最短(即权值最小)边，假定为(vi, vj)，其中vi∈U，vj∈V-U，并把该边(vi, vj)和顶点vj分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后把所有n个顶点都并入到生成树T的顶点集，此时U=V，TE中包含有n-1条边，T就是最后的到的最小生成树

简单概括： 初始时，有TE=空，U= , V1∈V。Prim算法描述为:从G中选择一个顶点仅在V中，而另一个顶点在U中，并且权值最小的边加入集合TE中，同时将该边仅在V中的那个顶点加入集合U中。重复上述过程n-1次，直到U=V，此时T为G的最小生成树。

算法描述

  附设一个辅助数组minedge[vtxptr]，记录从U到V-U具有最小代价的边。对每个顶点v∈ V-U，在辅助数组中存在一个分量minedge[v]，它包括两个域,其中lowcost存储该边上的权值，ver域存储该边的依附在U中的顶点。Minedge[v]=min{cost(u， v)，u∈U}，(cost(u， v)表示该边的权)。

算法描述

typedef int VRType;
typedef struct
{
    ertexType Ver;
    VRType lowcost;
}minedge[MaxVertexMum];         //从顶点集u到V-U的代价最小的边的辅助数组

void Prim(MGraph G，VertexType u, int n)
{
    //采用邻接矩阵存储结构表示图
    int k, v，j;
    k=vtxNum(G，u);             //取顶点u在辅助数组中的下标
    for(v=0; v<n; v++){        //辅助数组初始化
        if(v!=k) 
        {
            minedge[v].ver=u;
            minedge[v].lowcost=G.arcs[k][v];
        }
    }
    minedge[k].lowcost=O;       //初始，U= {u}
    for(j=1; j<n; j++) {        //选择其余的n-1个顶点
        k=min(minedgelj]);      //1≤j≤n-1，找一个满足条件的最小边(u，k)，u∈u,k∈V-u
        printf(minedgeLk].ver, G.vexs[k] ); //输出生成树的边
        minedge[k].lowcost=0;               //第k个顶点并入u
        for(v=0; v<n; v++) {
            if(G.arcs[k][v]<minedge[v].lowcost)         //重新选择最小边
            {
                minedge[v].ver=G.vexs[k];
                mindege[v].lowcost=G.arcs[k][v];
            }
        }
    }
    
}

普里姆算法的时间复杂度是O(n2)

例1

试用Prim算法构造（a）图的最小生成树，要求分步给出构造过程
普里姆算法示例.png

分析
  算法一开始取U={1}，然后到V-U中找一条代价最小且依附于顶点1的边，(u0，v0)=(1，3)(代价最小为1)，将v0=3加入集合U中，修改辅助数组中的值。使minedge[3].lowcost=0，以表示顶点3已并入U，由于边(3，6)上的权值是一条最小(为4)且依附于顶点集U中顶点的边，因此修改minedge[6]的值，依此类推，直到U=V，其过程如表所示。

普里姆算法示例分析.png

例2

试用Prim算法构造下图的最小生成树，画出所有可能的情况。

普里姆算法例题.png

解答

【解析】根据Prim算法构造，本题的最小生成树有的图有两种
【答案】最小生成树有的图有两种，如图所示
普里姆算法例题解答.png

2.克鲁斯卡尔(Krtskal)算法

算法思想

  假设G=(V，E)是一个具有n个顶点的连通网，T=(U，TE)是G的最小生成树，U的初值等于V，即包含有G中的全部顶点。T的初始状态是只含有n个顶点而无边的森林T=(v,Φ)。

  该算法的基本思想是:将图G中的边按权值从小到大的顺序依次选取E中的边(u,v)，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边;若选取的边使生成树T形成回路，则将其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T即为最小生成树。

例

试用克鲁斯卡尔(Krtskal）算法构造(a)图的最小生成树，要求分步给出构造过程
克鲁斯卡尔算法示例.png

过程

按照权值递增顺序考虑(1, 3)，(4, 6)，(2, 5)，(3, 6)，(1, 4)，(2, 3)，(3, 4)，(1, 2)，(5, 6)，(3, 5)
因为前四条边上的权值最小，而且又满足不在同一个连通分量上(不形成回路)的条件，所以依次将它们加入到T中。接着考虑当前权值最小的边(1, 4)，因该边的两个端点在同一个连通分量上(即形成回路)，故舍去。然后选择边(2, 3)加入到T中，便得到要求的一颗最小生成树

算法描述

Kruskal(G)
{
    //求连通网G的一棵MST
    T=(v，Φ);               //初始化T为只含有n个顶点而无边的森林，按权值升序对边集E中的边进行排序，结果存入E[0…e-1]中
    for(i=0; i<e; i++)          //e为图G中边总数
    {
        //取第i条边(u, v);
        if(u和v分别属于两棵不同的树) then;
            T=T U{(u，v)};
        if(T已经是一棵树) then;
            return T;
    }
    
    return T;
}

克鲁斯卡尔算法的时间复杂度为O(eloge)。

注意: 一个网中，若有权值相同的边，则其最小生成树不一定唯一;若所有边的权值均不相同，则其最小生成树是唯一的。

图的上一篇-图的运算
图的下一篇-最短路径和拓扑排序

分享到：