朱刘算法 朱、刘算法:求最小树形图权值【最小树形图模板】

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

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

  今天我们就来浅谈一下最小树形图的问题。大题上完整的朱、刘算法是由四个大步骤组成的:1、求最短弧集合E2、判断集合E中有没有有向环,如果有转步骤3,否则转43、收缩点,把有向环收缩成一个点,并且对图重新构建,包括边权值的改变和点的处理,之后再转步骤1。

4、展开收缩点,求得最小树形图。  因为我们ACM一般情况下都是在考察队最小树型图的权值问题,所以一般省略步骤4,对于其环的权值和在中间处理过程中就可以处理完毕。

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

代码实现:   for(int i=1; i<=n; i )if(i!=u&&!flag)//u作为图的根节点,flag【i】为1的情况就是表示这个点在某个有向环里边,并且他不是这个有向环的代表点(缩点) { w=INF, pre = i;//首先让当前点的前驱点为自己。

for(int j=1; j<=n; j )if(!

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

   int i; for(i=1; i<=n; i ) { if(i!

=u&&!flag) { 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。

对于收缩完之后会形成一个新的图,图的变化规律是这样的: 上图变换成语言描述:如果点u在环内,如果点k在环外,并且从k到u有一条边map【u】【v】=w,并且在环内还有一点i,使得map【i】【k】=w2,辣么map【k】【收缩点】=w-w2;基于贪心思想,对于环的收缩点i和另外一点k(也在环内),对于环外一点j,如果map【k】【j】 <> <>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 = 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[j] > w[k][j]) w[j] = w[k][j]; if(w[j][k]处理完4之后,我们就回到步骤1,继续找最小弧集E,最后找到了一个没有环的最小弧集E之后,对于没有弧的集合E中的所有边(包括能将收缩点展开的边)就是我们要求的最小树形图的边集。

 因为我们ACM一般求的都是最小树形图的权值,所以我们一般不需要展开收缩点,在处理环的时候,直接将其边权值记录下来就好,当找到一个没有环的集合E的时候,对其中的最后边权值进行加和即可,对于最后这部分的加权,代码实现:  if(i>n)//这块代码是紧接着代码2之后的部分,如果枚举了所有点i都没有发现有向环,辣么就是找到了这个最终集合。

{ for(int i=1; i<=n; i )if(i!

=u && !flag) ans =w[pre];//最后对这个最后的集合E里边所有边加和即可。 return ans; }完整的朱、刘算法代码实现(没有展开收缩点的):  void init()//不能少了初始化的内容{ memset(vis, 0, sizeof(vis)); memset(flag, 0, sizeof(flag)); for(int i=0; i<=n; i ) { w = INF; for(int j=i 1; j<=n; j ) w[j]=w[j]=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) { w=INF, pre = i; for(int j=1; j<=n; j )if(!

flag[j] && w[j]n) continue; //最后能找到起点(根)或者是走过的点已经超过了n个,表示没有有向环 break; } } if(i>n) { for(int i=1; i<=n; i )if(i!

=u && !flag) ans =w[pre]; 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 = 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[j] > w[k][j]) w[j] = w[k][j]; if(w[j][k]