最小树形图就是最小生成树在带权有向图上面的变种，也就是在有向图上找出一个边权和最小的有向树。这个问题需要给定一个带权的有向图以及有向树的根节点v。所谓有向树是指除了叶节点以外，所有节点都有指向其孩子节点的有向边。专业一点的说，“有向树（Directed Tree）是一个用于定义数据流或流程的逻辑结构。数据流的源点是根。数据流是单向分支离开根部到达目标，这个目标就是有向树的叶子。”。

求解最小树形图的第一个算法是1965年朱永津和刘振宏提出的复杂度为O(VE)的算法，该算法被称为朱-刘算法。在实现过程中，我们也可以表达为O(V³)的复杂度。

首先我们需要判断解是否存在。为了解决这个问题，我们只需要从指定的根节点v除法遍历一次就可以了。如果所有节点都可以被访问，那么解显然存在，否则不存在。另外，图中所有的自环也必须清除，因为这些自环显然不可能是最小树形图中的边。如果不知道什么是自环，请自行查阅图论相关定义。消除自环的目的是保证算法的时间复杂度。

下面是算法的流程：

1. 对于图中除了根节点v以外的节点，选择一条权值最小的入边。所有被选择的边构成了一个子图，如果这个子图不含有有向环，那么这就是问题的解，算法结束；否则进行下一步。
2. 我们需要收缩有向环，并且用一个新节点来代替。对于环中的点x，假定其选择边的权值为w₀，y为环外的点，z为环收缩后新的节点。如果存在边<x,y>，那么<z,y>的边权值与<x,y>相同。如果存在边<y,x>且权值为w，那么新边<y,z>的权值就是w-w₀。
3. 重复执行1、2两个步骤。

要保证算法O(VE)的复杂度，要做到找最小入边O(E)，找环O(V)，收缩O(E)。再加上由于收缩环最多只进行V-1次（自环已经被消除），所以时间复杂度为O(VE)。在步骤2中，x的出边权值不变是因为收缩环并没有影响边所指向的节点，而入边的权值之所以要变小，是因为当新边被选择之后，x原来选择的入边就会被取消选择，所以实际花费的代价就是w-w₀。

以下是2道可以提交的题目。

• [UVa]11183 - Teen Girl Squad
• [PKU]3164 - Command Network

• Relative Posts