最小树形图

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

最小树形图就是最小生成树在带权有向图上面的变种,也就是在有向图上找出一个边权和最小的有向树。这个问题需要给定一个带权的有向图以及有向树的根节点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
AP 9th Class Compute 说:
2022年9月24日 14:41

The Department of School Education has incorporated computer studies into several government and private organised schools in the state on the basis that computer education is crucial for everyone. AP 9th Class Computer Question Paper Download the AP 9th Computer Model Paper 2023 Pdf, which includes the solutions to all Computers-related lessons. The computer education practise question paper was prepared and recommended by subject specialists and teaching staff from a reputable educational institution.


登录 *


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