本文主要是介绍有向图的最小树形图(朱刘算法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
最小树形图的定义:
设G=(V,E)是一个有向图,如果具有下述性质:
(1)G中不包含有向环
(2)存在一个顶点vi,它不是任何弧的终点,而V的其他顶点都恰好是唯一的一条弧的终点,则称G是以vi为根的树形图。
最小树形图就是有向图G=(V,E)中以vi为根的树形图中权值和最小的那个。显而易见,对于不同的vi,得到的最小树形图是不一样的,甚至有可能不存在。
1.基本算法
使用的是朱刘算法(Edmonds朱永津和刘振宏在1965年发表的)。下面都指定为根的顶点是v0
最小树形图基于贪心和缩点的思想。所谓缩点,就是将几个点看成是一个点,所有连到这几个点的边都视为连到收缩点,所有从这几个点连出的边都视为从收缩点连出。
(1)求最短弧集
从所有以vi(i≠0)为终点的弧中取一条最短的,若对于点vi,没有入边,则不存在最小树形图,算法结束;如果能取,则得到由n-1个点和n-1条边组成的图G的一个子图G',该子图的权值一定是最小的,但是不一定是一棵树。
(2)检查E0
若E0没有有向环且不含收缩点,则计算结束,E0就是G的以v0为根的最小树形图。若E0没有有向环,但含收缩点,则转步骤(4),若E0含有有向环C,则转入步骤(3)。
(3)把G中的C收缩成点u,对于图G中两端都属于C的边都被收缩掉了,其他弧仍保留,得到一个新的图G1,G1中以收缩点为终点的弧的长度要变化,变化的规律是:设点v在环C中,且环中指向v的边长为w,点v'不在环C中,则对于每一条边<v',v>,在G1中有边<v',u>与其对应,且权值WG1(<v',u>)=WG(<v',v>)-W。对于图G中以环C为起点的边<v',v>,在图G1中有边<u,v'>,则WG1(<u,v'>)=WG(<v,v'>)。需要注意的是,在此步生成的图G1中可能存在重边
对于图G和G1
1)如果图G1中没有以v0为根的最小树形图,则图G中也没有
2)如果图G1中有以v0为根的最小树形图,则可以按照步骤(4)中的展开方法得到图G中的最小树形图。
因此,此时需要将G1代入步骤(1)作为图G继续进行计算,反复计算直到图G1的最小树形图求出。
(4)展开收缩点
如果图G1的最小树形图T1已经求出,那么所有T1中的弧都属于T。将图G1的一个收缩点u展开成环C,从C中去掉与T1中弧有相同终点的弧,其他弧都属于T。
总结:求一个图G0的最小树形图,先求出最短弧集合E0。若E0不存在,则图G0的最小树形图不存在。若E0存在且不含有有向环,则E0就是T0中所有的边。如果E0存在且含有有向环,则收缩有向环成一个点u,并形成图G1,继续求G1的最小树形图直到图Gi,若图Gi无最小树形图,则图G0也不存在最小树形图,若图Gi有最小树形图Ti,则逐层展开得到T0.
在计算的过程中可以发现,图Gi与图Gi-1的最小树形图的权值差正好是被缩掉的环的权值和,在这条性质的影响下,如果不需要直到最终的T0中到底有哪几条边,只需知道T0的权值时,可以不需要展开。
时间复杂度分析:对于最小树形图的算法,最多会进行n-2次缩点,每次缩点以及边权修改的时间复杂度为O(n^2),所以,最小树形图的时间复杂度为O(n^3)。
对应例题:传送门
题解:跟据题目要求建图,然后就是朱刘算法的板子了
附上代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>using namespace std;const int inf=0x3f3f3f3f;
const int maxn=1005;struct point{double x,y;
};
point p[maxn];double dis(point a,point b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}struct node{int u,v;double len;
};
node edge[maxn*maxn];int pre[maxn],id[maxn],vis[maxn];
double in[maxn];double dir_mst(int root,int n,int m)
{double ans=0;while(1){for(int i=0;i<n;i++){in[i]=inf;}//找最短弧集for(int i=0;i<m;i++){int u=edge[i].u,v=edge[i].v;if(edge[i].len<in[v]&&u!=v){pre[v]=u;in[v]=edge[i].len;}}for(int i=0;i<n;i++){if(i==root){continue;}if(in[i]==inf){//如果某点入度为0,必定找不到return -1;}}//id为环的序号memset(id,-1,sizeof(id));memset(vis,-1,sizeof(vis));in[root]=0;int cnt=0;//找环for(int i=0;i<n;i++){ans+=in[i];int v=i;while(vis[v]!=i&&id[v]==-1&&v!=root){vis[v]=i;v=pre[v];}if(v!=root&&id[v]==-1){for(int u=pre[v];u!=v;u=pre[u]){id[u]=cnt;}id[v]=cnt++;}}if(cnt==0){break;}for(int i=0;i<n;i++){if(id[i]==-1){id[i]=cnt++;}}//建立新图for(int i=0;i<m;i++){int u=edge[i].u,v=edge[i].v;edge[i].u=id[u];edge[i].v=id[v];if(id[u]!=id[v]){edge[i].len-=in[v];}}n=cnt;root=id[root];}return ans;
}int main()
{int n,m;while(~scanf("%d%d",&n,&m)){for(int i=0;i<n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);}for(int i=0;i<m;i++){scanf("%d%d",&edge[i].u,&edge[i].v);--edge[i].u;--edge[i].v;if(edge[i].u!=edge[i].v){edge[i].len=dis(p[edge[i].u],p[edge[i].v]);}else{edge[i].len=inf;}}double ans=dir_mst(0,n,m);if(ans==-1){printf("poor snoopy\n");}else{printf("%.2f\n",ans);}}return 0;
}
这篇关于有向图的最小树形图(朱刘算法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!