胡广.top

最小生成树问题

最小生成树问题

最小生成树问题指给定一张无向连通图G = (V,E),选取一个E的子集T,使得图G = (V,T)仍然是连通的且\sum_{e \in T}{e.\omega}尽可能小

显然,T中不能有环,不然可以简单的删去一条环边,又要保证连通,\mid T \mid = \mid V \mid -1

下面将论及两种MST的算法Kruskal和Rrim

最小生成树的形成

假定有一个连通无向图G = (V,E)和权重\omega,准备找出图G的一个最小生成树,本章讨论的两种方法都可以用以下过程来描述:

  1. $A$是个空集

  2. 当A还不是一个生成树时

    1. 找到一条边e使得将e加入A之后,A仍然是最小生成树的一个子集

    2. 将e加入A

  3. $A$即为所求的最小生成树

这两种算法全部的奥妙都在于如何找到符合要求的边e,满足这种性质的边也被称作安全边.

现在来介绍一条辨认安全边的规则

判断安全边

首先,定义切割的概念

无向图G = (V,E)的一个切割是V的一个划分(S,V-S)

如果有一条边(u,v) \ u \in S \ \land v \in V-S称这条边横跨切割(S,V-S)

如果集合A中没有横跨(S,V-S)的边,称(S,V-S)尊重集合A

在所有横跨(S,V-S)的边中权重最小的边称轻量级边

以上打虚线的是集合A

框出的是尊重集合A的分割(S,V-S)

边(c,d)是轻量级边

定理

  • 假设G = (V,E)是一个带权无向连通图

    A是E的一个子集
    且A是某最小生成树的子集

    (S,V-S)是尊重A的一个切割
    e是横跨(S,V-S)的一个轻量级边

  • 那么边e对A是安全的

证明

假设T是一颗包括A的最小生成树,且T不包含e

  • $T$中必有且仅有一条简单路径$e.u \leadsto e.v$

    且这条路径横跨切割$(S,V-S)$

    • 其上必至少有一边e’横跨切割(S,V-S)
  • 因为e是横跨(S,V-S)的一个轻量级边
    • 用e替代e’不会使情况变坏
  • 又有e \notin A
    • $e$可以被加入$A$中
  • $(S,V-S)$是尊重$A$的一个切割
    • 加入e不会造成环

边e对A是安全的

推论

  • 假设G = (V,E)是一个带权无向连通图

    A是E的一个子集
    且A是某最小生成树的子集
    C=(V_C,E_C)是森林G_A = (V,A)中的一个连通分量

    如果边e是连接了C和G_A中另一连通分量的一条轻量级边

  • 这条边是安全的

$Kruskal$算法

在这种算法中,考虑A = ( V , \emptyset )

不断地向A加入最小的连通两个分量的边

通过查并集可以快速地检查一个边是否连接了同一棵树,用Union(u,v)来合并两个集合

def KruskalMST(G):
    A = emptySet()
    for v in G.V:
        v.father = v
    sort( G.E ,key = weight )
    for (u,v) in G.E:
        if  u.father != v.father:
            A.insert((u,v))
            Union(u,v)
    return A

时间消耗

  1. 第一个for$\mathrm{O}(V)$

  2. 排序\mathrm{O}(E\log{E})

  3. 第二个循环\mathrm{O}(E)

  4. 所有的Nuion(u,v)$\mathrm{O}(V\log{V})$

  • 图是连通的,有V \le E + 1

  • 又有E

    • 有\mathrm{O}(E\log{E}) \approx \mathrm{O}(V\log{V})

总时间\mathrm{O}(E*\log{V})

$Prim$算法

在这种算法中A中的边永远构成一颗树

不断将连接A内和A外的轻量级边加入A

直到完成

为了决定下一个取哪条边

对于每个节点维护一个key属性,为它到A中的所有边的最小权重

再用key属性维护一个优先队列,用来决定下一个接谁

def PrimMST(G):
    A = emptySet()
    for u in G.V
        u.key = INF
        u.pi = NIL
        u.done = False
    r = randomSelect(G.V)
    r.key = 0
    Q = priorityQueue({r},key = key)
    while not Q.empty():
        u = Q.top()
        if not u.done:
            for v in G.Adj[u]:
                if  not v.done and weight(u,v) < v.key:
                    v.pi = u
                    v.key = weight(u,v)
                    Q.push(v.key,v)
            u.done = True
            A.insert(u.pi,u)
        Q.pop()

时间消耗

  1. 第一个初始化循环\mathrm{O}(V)

  2. 遍历所有的Adj[]耗时\mathrm{O}(E)

  3. 优先队的push()和pop()$\mathrm{O}(E\log{E})$

总时间\mathrm{O}(E\log{V})

但是如果使用斐波那契堆,优先队的消耗会变成\mathrm{O}(V\log{V}),总时间\mathrm{O}(E + V\log{V} )

Nemo

,
,