Skip to content

最小树形图

最小树形图就是给定一个有向图,求以某个给定顶点为根的有向生成树(也就是说沿着这N-1条有向边可以从根走到任意点),使权和最小。

解决这个问题有一个O(VE)的算法,是这样的:对于除根外的每个顶点,选择一条权最小的入边。如果选出来的V-1条边不构成环,则可以证明这些边就是满足要求的答案。如果存在环,则将环中的边收缩成一个顶点。设x是环中的点,y不是环中的点,v为新的顶点,w0为上一步中x选择的入边的权值,则原来的权值为w的边(x,y)变成权值为w的边(v,y),原来的权值为w的边(y,x)变成权值为w-w0的边(y,v)。这时最小树形图的答案就是环的权值和加上收缩以后的图的答案。

为什么收缩了以后要减小权值呢?很简单,最小树形图需要每个顶点选一条入边,顶点x当前已经有入边了,如果以后再给收缩后的顶点x选择权值为w的(原来属于x的)入边,就意味着已经选择的那条权值为w0的入边可以去掉了,也就是说选择这条边的代价应该是w-w0,所以就做这样的修改。

不过如果不固定根,我还不太知道如何用同样的复杂度解决,谁写过请教教我。

(发现自己最近表达能力很差,这个文章说得清楚些。)

示例程序(TJU2248,用邻接矩阵写的,O(V^3),比较简洁):
tju2248.cpp

3 Comments

  1. matrix67 wrote:

    “这个文章”的链接错了?

    Thursday, June 28, 2007 at 18:20 | Permalink
  2. TonyShaw wrote:

    这个链接怎么回事?

    Monday, November 16, 2009 at 16:25 | Permalink
  3. DMKaplony wrote:

    不定根的话,自己加一个点作为根,这个点到其他所有点的权值设为大于“原图的所有权值之和”的一个数,好像是这么回事,我也刚学,大家一起加油!
    ↖(^ω^)↗

    Monday, December 7, 2009 at 20:15 | Permalink

One Trackback/Pingback

  1. [zz] 最小树形图 « xiaoxins on Tuesday, June 7, 2011 at 23:41

    [...] 转载自:http://cuitianyi.com/blog/%E6%9C%80%E5%B0%8F%E6%A0%91%E5%BD%A2%E5%9B%BE/ [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*