朱、刘算法：求最小树形图权值个人理解+个人详解【最小树形图模板】

女爷i 2022-07-13 08:08 152阅读 0赞

什么是最小树形图？相信大家如果会过来看这篇文章，想必也应该对最小生成树有所了解的，最小生成树求的是无向图的一颗生成树的最小权值。我们的最小树形图就是来解决一个有向图的一颗生成树的最小权值，对于度娘来说，最小树形图是这样定义的：最小树形图，就是给有向带权图中指定一个特殊的点root，求一棵以root为根的有向生成树T，并且T中所有边的总权值最小。

通解最小树形图的一种算法是是1965年[朱永津][Link 1]和[刘振宏][Link 2]提出的复杂度为O(VE)的算法：朱、刘算法。

今天我们就来浅谈一下最小树形图的问题。

大题上完整的朱、刘算法是由四个大步骤组成的：

1、求最短弧集合E

2、判断集合E中有没有有向环，如果有转步骤3，否则转4

3、收缩点，把有向环收缩成一个点，并且对图重新构建，包括边权值的改变和点的处理，之后再转步骤1。

4、展开收缩点，求得最小树形图。

![Center][]

因为我们ACM一般情况下都是在考察队最小树型图的权值问题，所以一般省略步骤4，对于其环的权值和在中间处理过程中就可以处理完毕。所以我们这里就不多讨论第四个点了。

我们分步处理、

1、首先我们先求最短弧集合E，对于当前图如果有n个点（一个有向环的收缩点算作一个点），我们就要选出n-1个点，确定其入边的最短边，由其组成的一个集合我们就叫做最短弧集合E，如果我们枚举到某一个点的时候，它没有入边，那么说明不存在最小树形图，所以这个时候算法结束，回到主函数。

代码实现：

for(int i=1; i<=n; i++)if(i!=u&&!flag[i])//u作为图的根节点，flag【i】为1的情况就是表示这个点在某个有向环里边，并且他不是这个有向环的代表点（缩点）
                {
                    w[i][i]=INF, pre[i] = i;//首先让当前点的前驱点为自己。
                    for(int j=1; j<=n; j++)if(!flag[j] && w[j][i]<w[pre[i]][i])//枚举i的前驱点（从j能够到i的点），并且求其最短边，加入集合E中
                    {
                        pre[i] = j;//并且标记当前点的前驱点为j
                    }
                    if(pre[i]==i)return -1;//如果当前枚举到的点i没有入边，那么就不存在最小树形图（因为一颗树是要所有节点都是连通的啊）
                }

2、然后我们对集合E中的边进行判断，判断是否有有向环。刚刚的代码实现里边有一个前驱节点的存储，所以在这个部分，我们直接一直向前枚举前驱点即可，如果枚举的前驱点最终能够枚举到根节点，那么这一部分就不存在有向环，否则就存在，对于每一个点都进行向前枚举即可。

int i;
            for(i=1; i<=n; i++)
            {
                if(i!=u&&!flag[i])
                {
                    int j=i, cnt=0;
                    while(j!=u && pre[j]!=i && cnt<=n) j=pre[j], ++cnt;//对于每个节点都找前驱节点，看看能否成环。
                    if(j==u || cnt>n) continue; //最后能找到起点（根）或者是走过的点已经超过了n个，表示没有有向环
                    break;//表示有有向环
                }
            }

3、如果有有向环呢，我们需要对有向环进行缩点，既然我们是枚举到节点i的时候发现有有向环，我们不妨把有向环里边的点都收缩成点i。对于收缩完之后会形成一个新的图，图的变化规律是这样的：

![Center 1][]  
上图变换成语言描述：如果点u在环内，如果点k在环外，并且从k到u有一条边map【u】【v】=w，并且在环内还有一点i，使得map【i】【k】=w2，辣么map【k】【收缩点】=w-w2；

基于贪心思想，对于环的收缩点i和另外一点k（也在环内），对于环外一点j，如果map【k】【j】 <map【i】【j】，辣么map【i】【j】=map【k】【j】，因为是有向图，入收缩点的边要这样处理，出收缩点的边也要这样处理，对于刚刚三个步骤：收缩点，收缩点处理新图的边权值，以及基于贪心思想的最终处理点i的出边入边权值，后两者我们可以合并成一个操作，其分别的代码实现：

3、收缩点：

int j=i;
            memset(vis, 0, sizeof(vis));
            do
            {
                ans += w[pre[j]][j], j=pre[j], vis[j]=flag[j]=true;//对环内的点标记，并且直接对环的权值进行加和记录，在最后找到最小树形图之后就不用展开收缩点了
            }
            while(j!=i);
            flag[i] = false; // 环缩成了点i，点i仍然存在

4、处理收缩点后形成的图：

for(int k=1; k<=n; ++k)if(vis[k])  // 在环中点点，刚刚在收缩点的时候，已经把在环中的点进行标记了。
                {
                    for(int j=1; j<=n; j++)if(!vis[j])   // 不在环中的点
                        {
                            if(w[i][j] > w[k][j]) w[i][j] = w[k][j];
                            if(w[j][k]<INF && w[j][k]-w[pre[k]][k] < w[j][i])
                                w[j][i] = w[j][k] - w[pre[k]][k];
                        }
                }

处理完4之后，我们就回到步骤1，继续找最小弧集E，最后找到了一个没有环的最小弧集E之后，对于没有弧的集合E中的所有边（包括能将收缩点展开的边）就是我们要求的最小树形图的边集。

因为我们ACM一般求的都是最小树形图的权值，所以我们一般不需要展开收缩点，在处理环的时候，直接将其边权值记录下来就好，当找到一个没有环的集合E的时候，对其中的最后边权值进行加和即可，对于最后这部分的加权，代码实现:

if(i>n)//这块代码是紧接着代码2之后的部分，如果枚举了所有点i都没有发现有向环，辣么就是找到了这个最终集合。
            {
                for(int i=1; i<=n; i++)if(i!=u && !flag[i]) ans+=w[pre[i]][i];//最后对这个最后的集合E里边所有边加和即可。
                return ans;
            }

完整的朱、刘算法代码实现（没有展开收缩点的）：

void init()//不能少了初始化的内容
    {
        memset(vis, 0, sizeof(vis));
        memset(flag, 0, sizeof(flag));
        for(int i=0; i<=n; i++)
        {
            w[i][i] = INF;
            for(int j=i+1; j<=n; j++)
                w[i][j]=w[j][i]=INF;
        }
    }
    
    double directed_mst(int u)//u表示根节点
    {
        double ans=0;
        memset(vis, 0, sizeof(vis));
        while(true)
        {
            //求最短弧集合E
            for(int i=1; i<=n; i++)if(i!=u&&!flag[i])
                {
                    w[i][i]=INF, pre[i] = i;
                    for(int j=1; j<=n; j++)if(!flag[j] && w[j][i]<w[pre[i]][i])
                    {
                        pre[i] = j;
                    }
                    if(pre[i]==i)return -1;//也可以用dfs预处理判断凸的连通
                }
            //判断E是否有环
            int i;
            for(i=1; i<=n; i++)
            {
                if(i!=u&&!flag[i])
                {
                    int j=i, cnt=0;
                    while(j!=u && pre[j]!=i && cnt<=n) j=pre[j], ++cnt;
                    if(j==u || cnt>n) continue; //最后能找到起点（根）或者是走过的点已经超过了n个，表示没有有向环
                    break;
                }
            }
            if(i>n)
            {
                for(int i=1; i<=n; i++)if(i!=u && !flag[i]) ans+=w[pre[i]][i];
                return ans;
            }
            //有环，进行收缩，把整个环都收缩到一个点i上。
            int j=i;
            memset(vis, 0, sizeof(vis));
            do
            {
                ans += w[pre[j]][j], j=pre[j], vis[j]=flag[j]=true;//对环内的点标记，并且直接对环的权值进行加和记录，在最后找到最小树形图之后就不用展开收缩点了
            }
            while(j!=i);
            flag[i] = false; // 环缩成了点i，点i仍然存在
    
            //收缩点的同时，对边权值进行改变
            for(int k=1; k<=n; ++k)if(vis[k])  // 在环中点点
                {
                    for(int j=1; j<=n; j++)if(!vis[j])   // 不在环中的点
                        {
                            if(w[i][j] > w[k][j]) w[i][j] = w[k][j];
                            if(w[j][k]<INF && w[j][k]-w[pre[k]][k] < w[j][i])
                                w[j][i] = w[j][k] - w[pre[k]][k];
                        }
                }
        }
        return ans;
    }

[Link 1]: http://baike.baidu.com/view/310724.htm
[Link 2]: http://baike.baidu.com/view/2882877.htm
[Center]: /images/20220713/e1e73fedfc634f99aa2e230ea0c45aa2.png
[Center 1]: /images/20220713/0c9bf38b3a7847b1a3a6cac18242ac99.png