最小树形图,朱刘算法详解[转]

几句题外话

  1. 第一句题外话,也是最重要的一句:朱刘算法是有向图的最小生成树算法,Prim和Kruskal是无向图的最小生成树算法。一般而言,这两类算法不能通用
  2. 没错,朱刘算法的提出者是两位中国科学家:朱永津和刘振宏。国外相似的成果是Edmonds算法。
  3. 最后一句,也是最没用的题外话:朱刘算法是我学习数据结构与算法以来第一个感到难以完全理解的算法,断断续续看了两天,仍有些头绪没有理清楚。朱刘算法出现在ACM竞赛中,也出现在数学系研究生课程《网络优化》中,本来应该离我很遥远。但是你丫出现在数据结构与算法的习题当中,还能让人愉快地学习吗?但习题毕竟是习题,遇到了也不能不做。所以目前我只能就自己的掌握情况,谈谈对算法及其实现的理解。若未来某一天有了更深刻的理解,再做完善。
 

算法(本身并不难懂)

  1. 检查有向图是否存在自环,是否存在从根出发不可达的顶点。若存在自环,则去掉自环;若存在从根出发不可达的顶点,则不能生成最小树形图。
  2. 接1,现在所有顶点都可由根达到,可以生成最小树形图。检查每一条边,由此获取除根之外每一个顶点的最小入边,共有(V-1)条(V是顶点数)。
  3. 检查这(V-1)条边构成的子图中是否存在环。若不存在,则当前子图就是最小树形图,算法结束;否则,继续进行下一步,“缩点去环、重新构图”。
  4. 这一步,我们要做的是:把环中的某一条边(say, u–>v)删去,用另一条能达到v的外部边代替之,同时要保证权值的增量最小(为什么说增量?因为当初选的就是最小入边啊,现在替换掉它总权值当然增加了。)怎么做呢?对这个环上的每一个顶点,用其他入边的权值减去最小入边的权值,得到一系列增量(环上有数个顶点,每个顶点又有数个增量),选最小增量对应的那条入边,代替原来的最小入边。这样,我们破了环,同时保持增量尽可能小。
  5. 重复3、4。
下面的一张图(经典)体现的正是上述过程,请仔细体会

 
对上图举个例子,最小入边a7, a10, a8形成了一个环。我们看到,V5的增量是5-3=2,V4的增量是9-4=5,V6的增量是9-5=4、8-5=3,于是这个环的增量集合是{2, 5, 4, 3}。要使增量最小,我们要选择2为增量,于是删除边a8,用边a3代替。
 

实现(却需要一点trick)

需要什么trick呢?请看我对前辈模板的详细注释。

#define M 105	//最大顶点数
#define INFINITE (1<<31)
#define MYTYPE int

struct _edge	//边
{
	int from;
	int to;
	MYTYPE cost;
} edge[M*M];

int Pre[M];	//前驱
int ID[M];	//当前图-->重构图顶点标号的映射
int Vis[M];	//访问标记
MYTYPE In[M];	//记录顶点的最小入边

MYTYPE Directed_MST(int root, int NV, int NE)
{
	MYTYPE ret=0;

	while (1)	//开始迭代
	{
		//1.确定最小入边集
		for (int i=0; i<NV; ++i) In[i]=INFINITE;
		for (int i=0; i<NE; ++i)
		{
			int from=edge[i].from;
			int to=edge[i].to;
			if (edge[i].cost<In[to] && from!=to)	//忽略自环
			{
				In[to]=edge[i].cost;
				Pre[to]=from;
			}
		}
		//检查除根之外是否有不可达顶点
		for (int i=0; i<NV; ++i)
		{
			if(i==root) continue;	//除根之外
			if(In[i]=INFINITE) return -1;	//有不可达顶点
		}

		//2.找环
		for (int i=0; i<NV; ++i)
		{
			Vis[i]=-1;
			ID[i]=-1;
		}
		int cnt_node=0;	//把一个环看成一个点,环外的一个点还是一个点
		In[root]=0;

		for (int i=0; i<NV; ++i)	//计算当前最小入边集的权值和;统计有多少个环;重新给顶点编号
		{
			ret+=In[i];	//计算当前最小入边集的权值和
			int v=i;
			while (Vis[v]!=i && ID[v]==-1 && v!=root)	//对每个点回溯。若最后v回到了根,说明这个点不在环里;若最后v没回到根,说明v在环里。
			{
				Vis[v]=i;
				v=Pre[v];
			}
			if (v!=root && ID[v]==-1)	//v没回到根,说明v在环里
			{
				for (int u=Pre[v]; u!=v; u=Pre[u])	//标记环上的所有顶点为同一序号
				{
					ID[u]=cnt_node;
				}
				ID[v]=cnt_node;
				++cnt_node;
			}
		}
		if(cnt_node==0)	break;	//没有环(每次都回到根,跳过上一个for循环,cnt_node总是0),那么当前ret值就是最小树形图的边权和
		for (int i=0; i<NV; ++i)
		{
			if(ID[i]==-1)
			{
				ID[i]=cnt_node;
				++cnt_node;
			}
		}

		//3.重新构图,准备开始下一轮迭代
		for (int i=0; i<NE; ++i)
		{
			int to=edge[i].to;
			//重新构图
			edge[i].from=ID[edge[i].from];
			edge[i].to=ID[edge[i].to];
			if(edge[i].from != edge[i].to)
			{
				edge[i].cost-=In[to];	//放弃最小边(如果放弃是因为它在环里)所需要付出的代价,就是增量。这些增量又构成了一张新图,下一轮迭代处理这张新图。
				/*注意:
				Here's the tricky part!还记得算法本身是怎样做的吗?求出环上每个点若放弃最小入边所产生的增量,形成一个增量集合,选择集合中最小的增量。
				这里把环上的所有点都标成同一个序号,看成一个点,下一次迭代过程的第一步就是求这个“点”入边的最小权值,实际上求的就是环上所有点增量集合的最小值,也就是最小增量!
				*/
			}
		}

		//为下一轮迭代赋初值
		NV=cnt_node;
		root=ID[root];
	}

	return ret;
}

 

下面这张图展示了缩点的过程:

后记

经过三天左右的资料查阅和反复揣摩,我认为已经把从算法到实现都说清楚了:算法本身并不难懂,困难的地方在于理解前辈对算法的实现过程(所谓的“模板”)。当然如果真正理解了,也没什么大不了的。尽管如此,这个算法只是有向图最小生成树算法的一种,理论尚有纵深,所以如果有机会,深入学习一番也不错。

发表评论

邮箱地址不会被公开。 必填项已用*标注

请输入正确的验证码