最小树形图

张文泰 posted @ 2010年2月22日 06:27 in Art of Science with tags 图论 最小树形图 , 5132 阅读

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

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

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

下面是算法的流程:

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

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

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

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

本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter