图的生成树

　　定义1   对于无向图G和一棵树T来说，如果T是G的子图，则称T为G的树，如果T是G的生成子图，则称T是G的生成树。

　　定义2   对于一个边上具有权值的图来说，其边权值和最小的生成树称做图G的最小生成树。

　　定理1    对于一个图G，如果图中的边权值都不相同，则图的最小生成树唯一。

　　最小生成树

　　求无向图的最小生成树主要有Prim算法和Kruskal算法。

　　1.Prim算法

　　（1）基本算法

　　将图G中的所有点V分成两个顶点集合Va和Vb。在计算过程中Va中的点为已经选好连接入生成树的点，否则属于Vb。最开始的时候Va包含任意选取的图G中的一个点u，其余的点属于Vb，算法结束时所有与u连通的点属于Va，其余的点仍留在Vb中。如果算法结束时Vb不为空，说明图G的生成树不存在，只存在生成森林。

　　代码如下：

//直接实现，邻接矩阵存储图
const int maxn=101;
void Prim(int n,int dist[maxn],int map[maxn][maxn],int pre[maxn])
//n个点，dist[i]表示向外延伸的最短边长，map记录图信息，pre[]记录连接信息，
//dist之和最最小权值
{
    int i,j,k;
    int min;
    bool p[maxn];//记录该点是否属于Va
    for(i=2;i<=n;i++)
    {
        p[i]=false;
        dist[i]=map[1][i];
        pre[i]=1;
    }
    dist[1]=0;
    p[1]=true;
    for(i=1;i<=n-1;i++)//循环n-1次，每次加入一个点
    {
        min=INT_MAX;
        k=0;
        for(j=1;j<=n;j++)
        {
            if(!p[j]&&dist[j]<min)
            {
                min=dist[j];
                k=j;
            }
        }
        if(k==0)return;//如果没有点可以扩展，即图G不连通，返回
        p[k]=true;
        for(j=1;j<=n;j++)
        {
            if(!p[j]&&map[k][j]!=INT_MAX&&dist[j]>map[k][j])
            {
                dist[j]=map[k][j];
                pre[j]=k;
            }
        }
    }
}
//时间复杂度O(n^2);

//堆实现
/*使用堆来保存Vb中每一点到Va中所有点的最短边长并维护其最小值，
并在访问每条边的时候更新。先将所有的点插入堆，并将值赋为inf，
将根赋值为0，通过松弛技术进行更新。*/
//堆
struct HeapElement
{
    int key,value;
};
struct MinHeap
{
    HeapElement H[maxn];
    int size;
    int position[maxn];
    void init(){H[size=0].value=-INF;}
    void ins(int key,int value)
    void decrease(int key,int value)
    void delmin()
}H;
//边
struct edge
{
    int to,w,next;
}edge[maxm];
int N,M;
long long dist[maxn];
int head[maxn];
void Prim()
{
    int i,j,k;
    bool p[maxn]={0};
    H.init(true);
    for(i=1;i<=N;i++)
    {
        H.ins(i,INF);
        dist[i]=INF;
    }
    dist[1]=0;
    H.decrease(1,0);
    for(i=1;;)
    {
        p[i]=true;
        H.delmin();//删除堆顶元素
        for(k=head[i];k!=-1;k=edge[k].next)
        {
            if(!p[j]&&edge[k].w<dist[j=edge[k].to])
            {
                dist[j]=edge[k].w;
                H.decrease(j,dist[j]);
            }
        }
        if(H.size)i=H.H[1].key;
        //扩展Vb中的点，以便下次更新
        else break;
    }
}

/*用堆优化的Prim算法主要用于加速变较少的图的最小生成树的计算，特别是稀疏图。
总的时间复杂度是O((n+m)log n).当边较少时，这种算法相对直接实现的Prim算法来说
有很好的效果。*/

　　2.Kruskal算法

　　Kruskal算法基于贪心的思想，对于图G={V,E}，先构造G‘={V，Ø},然后依次向G’中添加E中未添加过的权值最小的边，如果这条边加入G‘中存在环，则去掉这条边，直到G’成为一棵树。

　　具体步骤：

　　①首先初始化，生成图G‘，并将E中的边按权值排序。

　　②从最小的边开始尝试加入到图G’中，如果当前便加入后存在环，则弃掉当前边，否则标记当前边并计数。

　　③遍历所有边后，如果选择的边数等于n-1，则生成最小生成树，计算步骤②所选择的边的权值之和，否则最小生成树不存在，只存在最小生成森林，但是Kruskal算法不需要反复运行，当前结果就是图G的最小生成森林。

　　算法的关键在于如何判断新加入的边会使图G‘产生环，这里使用并查集，并查集中的一个等价类代表图G’中的一个连通分量，也就是一棵树，如果新加入边的两端在并查集的一个等价类中，说明存在环，需要舍掉这条边；否则保留当前边，并合并涉及的两个等价类。

　　代码如下：

//并查集
const in maxn=1010;
int UFSTree[maxn];
int find(int x);
void merge(int x,int y)
//Kruskal
const int maxm=100010;
struct node
{
    int a,b;//边的起点和终点
    int w;
    bool select;
}edge[maxm];
bool cmp(node a,node b)
{
    if(a.w!=b.w)return a.w<b.w;
    else if(a.a!=b.a)return a.a<b.a;
    else return a.b<b.b;
}
void Kruskal(node *edge,int n,int m)
{
    int k=0;
    int i,x,y;
    sort(edge+1,edge+1+m,cmp);
    for(i=1;i<=m;i++)
    {
        if(k==n-1)break;//合并了n-1条边，结束
        x=find(edge[i].a);
        y=find(edge[i].b);
        if(x!=y)
        {
            merge(x,y);
            k++;
            edge[i].select=true;
        }
    }
}

　　时间复杂度为O(mlog m + m),即主要的时间都花在边的排序上了。个人觉得该算法好理解、好操作。

　　次小生成树

　　次小生成树的边的权值和可能等于最小生成树的权值和，或者略大。

　　定义1    设G={V,E}是连通的无向图，T是图G的一棵最小生成树。如果有另一棵树T1，T1≠T，满足不存在T‘，T’≠T，w(T')<w(T1)，则称T1是图G的次小生成树。

　　定理1     存在边(u,v) ∈T和(x,y)不属于T满足T(u,v)U(x,y)是图的一棵次小生成树。

　　基于定理1，那么所有的T(u,v)U(x,y)刚好构成了T的邻集，则T的邻集中权值最小的就是次小生成树了。（定义由最小生成树T进行一次可行交换得到的新的生成树所组成的集合，称为树T的邻集，记为N(T)。所谓的可行交换即去掉T中的一条边，再新加入图G中的一条边，使得新生成的图仍为树。）

　　效率较高的做法是先加入(x,y)，对于一棵树，加入(x,y)后一定成为环，如果删去环上除(x,y)以外的最大的一条边，会得到加入(x,y)时权值最小的一棵树。如果能够快速计算最小生成树中点x到y之间路径中最长边的长度，这个问题就能很好地解决。最小生成树中x到y的最长边可以使用树形动态规划或者LCA等方法在O(n^2)的时间复杂度内算出。如果使用Kruskal算法求最小生成树，可以在算法的运行过程中求出x到y路径上的最长边，因为每次合并两个等价类的时候，分别属于两个等价类的两个点间的最长边一定是当前加入的，按照这条性质记录的话就可以求出所有值了。为了便于合并时的修改，需要记录每个集合都有哪些点，可以写一个类似邻接表的数据结构，将以i为代表元的集合的所有点作为i的邻接点进行存储。

　　具体实现如下：

　　在Kruskal算法的基础上进行修改，加入对x,y两点在最小生成树上路径中最长边的计算，存入length[][]数组。使用链式前向星记录每个集合都有哪些点。为了合并方便，除了head[]记录每条邻接表的头结点位置外，end[]记录每条邻接表尾节点的位置便于两条邻接表合并。mst为最小生成树的大小，secmst为次小生成树的大小。

　　代码如下：

//并查集
const in maxn=1010;
int UFSTree[maxn];
int find(int x);
void merge(int x,int y)
//Kruskal
const int maxm=100010;
struct node
{
    int a,b;//边的起点和终点
    int w;
    bool select;
}edge[maxm];
bool cmp(node a,node b)
{
    if(a.w!=b.w)return a.w<b.w;
    else if(a.a!=b.a)return a.a<b.a;
    else return a.b<b.b;
}
//链式前向星的数据结构
struct node1
{
    int to,next;
};
node1 link[maxn];//边数组,注意这里是maxn，而不是maxm，是类似的链式前向星
int il;//边数组中数据的个数
int head[maxn];//邻接表的头结点位置
int end[maxn];//邻接表的尾节点位置
int length[maxn][maxn];//每两点在最小生成树上路径中最长边长

void Kruskal(node *edge,int n,int m)
{
    int k=0;
    int i,x,y;
    //初始化邻接表，对于每个节点添加一条指向其自身的边，表示以i为代表元的集合只有i
    for(il=0;il<n;il++)
    {
        link[il].to=il+1;
        link[il].next=head[il+1];
        end[il+1]=il;
        head[il+1]=il;
    }
    sort(edge+1,edge+1+m,cmp);
    for(i=1;i<=m;i++)
    {
        if(k==n-1)break;//合并了n-1条边，结束
        if(edge[i].w<0)continue;
        x=find(edge[i].a);
        y=find(edge[i].b);
        if(x!=y)
        {
            //修改部分，遍历两个节点所在的集合
            for(w=head[x];w!=-1;w=link[w].next)
            {
                for(v=head[y];v!=-1;v=link[v].next)
                {
                    int pp=link[w].to,qq=link[v].to;
                    length[pp][qq]=length[qq][pp]=edge[i].w;
                }
            }
            link[end[y]].next=head[x];
            end[y]=end[x];
            merge(x,y);
            k++;
            edge[i].select=true;
        }
    }
}

int main()
{
    //先初始化和建图，然后进行下面的操作
    int mst,secmst;
    Kruskal(edge,n,m);
    mst=0;
    for(i=1;i<=m;i++)
    {
        if(edge[i].select)mst+=edge[i].w;
    }
    secmst=INF;
    for(i=1;i<=m;i++)
    {
        if(!edge[i].select)secmst=min(secmst,mst+
                                      edge[i].w-length[edge[i].a][edge[i].b]);
    }
}

　　整个算法运行了一次Kruskal算法，时间复杂度是O(mlogm),同时又对整个length[][]进行赋值，时间复杂度O(n^2),最终又进行了时间复杂度为O(m)的遍历，所以总的时间复杂度为O(mlogm+n^2)。

　　有向图的最小树形图

　　首先看一个例子，有一处水源给附近的菜地供水，在没有抽水机的情况下，水只能从高处流向低处，每修一条水渠都有一定的花费，问怎样修才能使花费最低。考虑到水的流向，要求生成的最小生成树必须以水源为根，而且需要能够由根到达所有的节点。这就是最小树形图问题。

　　定义1    最小树形图的定义：

　　设G=(V,E)是一个有向图，如果具有以下性质：

　　(1)G中不包含有向环；

　　(2)存在一个顶点Vi，他不是任何弧的终点，而V的其他顶点都恰好是唯一的一条弧的终点。则称G是以Vi为根的树形图。

　　基本算法:

　　最小树形图基于贪心的思想和缩点的思想。所谓缩点，就是将几个点看成一个点，所有连接到这几个点的边都视为连到收缩点，所以从这几个点连出的边都被视为从收缩点连出。

　　下面根节点取为V0.

　　（1）求最短弧集合E0

　　从所有以Vi（i!=0）为终点的弧中去一条最短的，若对于点Vi，没有入边，则不存在最小树形图，算法结束；如果能取，则得到由n个点和n-1条边组成的图G的一个子图G‘，该子图的权值一定是最小的，但是不一定是一棵树。

　　（2）检查E0

　　若E0没有有向环且不含收缩点，则计算结束，E0就是G的以V0为根的最小树形图。若E0没有有向环、但含收缩点，则转步骤（4），若E0含有有向环，则转入步骤（3）。

　　（3）收缩G中的有向环

　　把G中的C收缩成点u，对于图G中两端都属于C的边被收缩掉了，其他弧扔保留，得到一个新的图G1，G1中以收缩点为终点的弧的长度要变化，变化的规律是：设点v在环C中，且环中指向v的边长为w，点v'不在环C中，则对于每条边<v',v),在G1中有边<v',u>与其对应，且权重为w(<v',v>)-w；对于图G中以环C为起点的边<v,v'>，在图G1中有边<u,v'>,权重为w(<v,v'>)。在此步生成的图G1中可能存在重边。

　　对于图G和图G1：

　　①如果图G1中没有以V0为根的最小树形图，则图G也没有。

　　②如果图G1中有以V0为根的最小树形图，则可以按照步骤（4）的展开方法得到图G的最小树形图。

　　因此，此时需要将G1带入步骤（1）做为图G继续进行计算，反复计算直到图G1的最小树形图求出。

　　（4）展开收缩点

　　如果图G1的最小树形图T1已经求出，那么所有T1的弧都属于T。将图G1的一个收缩点u展开成环C，从C中去掉与T1中有相同终点的弧，其他弧都属于T。

　　在计算的过程中可以发现，图Gi与图Gi-1的最小树形图的权值差正好是被缩掉的环的权值和，在这种性质的影响下，如果不需要知道最终的T0中到底需要那几条边，只需要知道T0的权值时，可以不需要展开。

　　下面给出只是求权值的代码：

double zhuliu(int n,double map[maxn][maxn])
{
    bool vis[maxn];
    bool flag[maxn];//缩点标记为true，则该点已经被收缩，否则仍然存在
    int pre[maxn];
    double sum=0;
    int i,j,k;
    for(i=0;i<n;i++)
    {
        flag[i]=false;
        map[i][i]=INF;
    }
    pre[0]=0;
    while(true)
    {
        //求最短弧集合E0
        for(i=1;i<n;i++)
        {
            if(flag[i])continue;
            pre[i]=i;
            for(j=0;j<n;j++)
            if(!flag[j]&&map[j][i]<map[pre[i]][i])pre[i]=j;
            if(pre[i]==i)return -1;
        }
        //检查E0
        for(i=1;i<n;i++)
        if(!flag[i])
        {
            //从当前点开始找环
            for(j=0;j<n;j++)vis[j]=false;
            vis[0]=true;
            j=i;
            do
            {
                vis[j]=true;
                j=pre[j];
            }while(!vis[j]);
            if(!j)continue;//没有找到环
            i=j;
            //将整个环的权值保存，累计入原图的最小树形图
            do
            {
                sum+=map[pre[j]][j];
                j=pre[j];
            }while(j!=i);
            j=i;
            //对与环上的点有关的边，修改边权
            do
            {
                for(k=0;k<n;k++)
                if(!flag[k]&&map[k][j]<INF&&k!=pre[j])
                map[k][j]-=map[pre[j]][j];
                j=pre[j];
            }while(j!=i);
            //缩点，将整个环缩成i号点，所有与环上的点有关的边权转移到点i
            for(j=0;j<n;j++)
            {
                if(j==i)continue;
                for(k=pre[i];k!=i;k=pre[k])
                {
                    if(map[k][j]<map[i][j])map[i][j]=map[k][j];
                    if(map[j][k]<map[j][i])map[j][i]=map[j][k];
                }
            }
            //标记环上的其他的点被缩掉
            for(j=pre[i];j!=i;j=pre[j])flag[j]=true;
            //当前环缩点结束，形成新的图G‘，跳出继续求G’的最小树形图
            break;
        }
        //如果所有的点都被检查，且没有环存在，
        //现在的最短弧集合E0就是最小树形图，累计入sum,算法结束
        if(i==n)
        {
            for(i=1;i<n;i++)if(!flag[i])sum+=map[pre[i]][i];
            break;
        }
        return sum;
    }
}

　　时间复杂度为O(n^3)。

参考文献《图论及应用》哈尔滨工业大学出版社

特此申明：严禁转载

2014-02-19