最小树形图算法

Published: by Creative Commons Licence

  • Tags:

最小树形图

给定一副有向图,选定某个特定的结点作为根,我们希望能找到一株树,树中所有顶点对于根是可达的,且从根到每个顶点的路径都是唯一的,这样的图称为树形图。

对于所有这类树形图中,总边权最小的为最小树形图。

朱刘算法

我们找到每个顶点(除了根)的最小权入边找到,假如这些边组成的树是无环树,可以证明这是一个最小树形图。实际上在这样一个无环树中,从任意一个顶点沿着反向边移动,最后一定会抵达根。而最小是很显然的,因为不存在更小的。

当然假如运气没那么好,我们就需要一些额外操作了。

命题1:如果由最小权入边组成的树中有环,设环的长度为k,那么可以保证至少存在一个最小树形图,包含该环中k-1个边。

假设最小树形图中离根最近(即从根出发到该顶点经过边数最少)的环上顶点为u,很显然u的最小权入边不包含于树形图中。但是对于环上的边$(u,v)$,如果不存在树形图中,我们可以切断v与父亲的边,而加入$(u,v)$,而新图总权不会增大。不断这样操作,就可以将另外$k-1$条边都加入到图上。

我们可以将环合并为一个顶点,所有进入环内顶点的边的目的地修改为合并后的顶点,同时对于某个顶点v的入边,其权值还需要减去v的最小权入边的权,因为当选择这条边加入最终结果时,会断开v的最小权入边。

由于命题1的存在,我们保证我们得到的树形图中,保护环上的k-1条边,换言之,我们可以认为环上的顶点始终是连通的,因此合并为一个顶点并不会影响最终结果(其只能接受一个入边且始终连通),我们可以将其作为一个顶点处理。并在缩点后的图上重复调用这个流程,直到所有不存在环。

假如最终图除了根以外,还存在其余顶点没有最小权入边,那么就不存在树形图,否则就找到了树形图。

可以通过并查集找环,最多发生$V-1$此缩环,每次找环最多$O(E)$时间复杂度,因此总的时间复杂度为$O(VE)$。

Tarjan的最小树形图算法

详细的可以见论文

Tarjan提供了朱刘算法的快速实现方案,预处理的时间复杂度为$O(E\log_2V)$。之后可以多次以$O(V)$的时间复杂度找到以任意顶点为根的最小树形图。

下面讲一下我的实现方案。(这里并非是Tarjan的原来版本,而是基于它的原理我自己修改后的,但是保证了时间复杂度和空间复杂度)

首先我们必须保证图的连通性,即任意两个顶点之间都有互相抵达的路径。我们可以加入O(V)条边,将所有顶点串成一个环,并设置这些边的权为无穷,保证这些边不会被用来组成最小树形图即可。

我们维护一个栈,一开始任意选择一个顶点加入到栈中。之后执行下面流程:

1.如果所有顶点都缩为了一个顶点,则结束流程,否则进入步骤2。

2.为栈尾元素v找到最小入边(可以为每个顶点的入边维护一个最小堆),如果最小入边是自环,那么就找下一个,直到找到非自环的边(这里一定是可以成立的,因为我们一开始就保证了图的连通性)。

2.记边的起点为u,所在并查集的currentLevel为x。我们记录v.inEdge为边$(u,v)$。

3.如果x不曾被加入过栈中,我们将x加入栈中,并将x.outEdge设置为边$(u,v)$。之后回到步骤1。

4.新建一个新的结点代表整个环,记作q,将q.outEdge设置为x.outEdge,x.outEdge设置为$(u,v)$。将栈尾元素t和q所在并查集合并。同时需要将最小堆合并,我们这里可以采用可合并堆,我用的是左偏树,你们任意。合并之前,不要忘了将t的整个左偏树中的边的权减少t.inEdge的权值,这里可以使用惰性标记来保证$O(1)$的时间复杂度。之后将t.parent设置为q,并设置t.outNode为环上前一个元素(一般是栈前一个元素,对于x则是v)。不断退栈重复该过程,直到x出栈。

5.将q所在并查集的currentLevel设置为q。将q入栈。回到步骤1。

contract(V, E){
    remain = |V|;
    stack.push(one node in V);
    while(remain > 1){
        tail = stack.peek();
        minInEdge = null;
        while(true){
            minInEdge = tail.queue.remove();
            if(minInEdge.src.find() != minInEdge.dst.find()){
                break;
            }
        }
        x = minInEdge.src.find().currentLevel;
        if(!x.visited){
            x.visited = true;
            stack.push(x);
            x.outEdge = minInEdge;
            continue;
        }
        q = new node;
        q.visited = true;
        q.outEdge = x.outEdge;
        x.outEdge = minInEdge;
        last = x;
        while(true){
            t = stack.pop();
            t.queue.modify(-last.outEdge.weight);
            q.queue = mergeQueue(q.queue, t.queue);
            mergeDUS(q, t);
            t.parent = q;
            last.outNode = t;
            last = t;
            remain--;
            if(t == x){
                break;
            }
        }
        q.find().currentLevel = q;
        stack.push(q);
        remain++;
    }
    top = stack.pop();
}

上面的步骤就是预处理的流程。我们知道每次创建合并顶点,图上的顶点总数必定至少减1,因此整个流程处理的顶点总数仅为$O(V)$。步骤2最多执行$O(E)$次,每次时间复杂度为$O(\log_2V)$(来自同一顶点的入边可以仅保留最小权的那个)。步骤3每次都会往栈中加入一个未被标记的顶点,这些顶点一定是原来图上的顶点(不是合并后的顶点),因此最多执行$O(V)$次。步骤4的每次合并,都会减少图上只少一个顶点,因此合并最多发生$O(V)$此。而左偏树的合并的时间复杂度为$O(\log_2V)$。

因此加总后可以发现总的时间复杂度为$O(E\log_2V)$。

下面要说的是如何基于预处理,从中抽取出以顶点r为根的最小生成树。一般的思路是从上往下剖开最后缩成的合并顶点,但是tarjan版本则使用了从底至上的方案。我们将预处理阶段留在栈中的唯一顶点记作top。

1.如果r已经被标记或者r为top,则返回。

2.标记r所在的环上的所有顶点。并将除了r在环上的最小入边外其余所有环上的边加入到结果中。

3.通过outNode属性遍历环上的所有顶点x,并通过outEdge的终点这个属性,找到x代表的子树中的根y,对y调用这个流程。

4.对r.parent调用这个流程。

因为每次调用这个流程,或者循环的过程中,都会至少标记一个新的顶点,每个顶点仅会被标记一次。整个图中剩下$O(V)$个顶点和$O(V)$条边,因此总的时间复杂度为$O(V)$。

dismantle(r, result){
    if(r == top || r.visited){
        return;
    }
    r.visited = true;
    trace = r;
    while(true){
        front = trace.outNode;
        frontRoot = trace.outEdge.dst;
        if(front == r){
            break;
        }
        front.visited = true;
        dismantle(frontRoot, result);
        result.add(trace.outEdge);
        trace = front;
    }
    dismantle(r.parent);
}

提供一道练习用的题目LUOGU4716