几句题外话

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

实现（却需要一点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;
}

 

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

后记

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