Skip to content

Latest commit

 

History

History
77 lines (67 loc) · 3.62 KB

6A.md

File metadata and controls

77 lines (67 loc) · 3.62 KB

Kruskal算法

　　Kruskal算法是解决最小生成树的经典算法，其思想比较直接：按权从小到大遍历所有边，有用的就留着。从整体上看，该算法会用选出的边，把图中所有的点逐渐连通起来。

数组 + 链环

　　这里的难点其实在于连通性的记录与维护。我们选择数组和单向链环的复合结构来解决：数组的角度看，可以快速查找任意编号点的记录；从单向链环的角度看，可以快速合并两个连通域。

type node struct {
    next *node          //指向连通域中下一节点，以构成单向链环
    mark int            //正数表示所属连通域编号（连通域首节点编号）
}                       //负数表示以此点为首的连通域中点的计数

我们用一个编号来来记录点所属的连通域，并在编号与此相同的点的记录中保存域中点的数目。

实现 & 分析

　　首先，对输入的边进行排序，以便于按权从小到大遍历。接着，把每个点视为独立连通域，再将其聚合至一个包含所有点的连通域。在此过程中，我们把规模小的连通域并入规模大的连通域。

func Kruskal_v2(roads []graph.Edge, size int) (uint, error) {
    if size < 2 || len(roads) < size-1 { return 0, errors.New("illegal input") }
    sort.Less[graph.Edge](edgeLess).Sort(roads)         //对边集排序

    nodes := make([]node, size)
    for i := 0; i < size; i++ {                         //初始化点的记录
        nodes[i].mark, nodes[i].next = -1, &nodes[i]
    }
    trace := func(id int) int {
        if nodes[id].mark < 0 {
            return id
        } else {
            return nodes[id].mark
    }   }

    sum := uint(0)
    for _, path := range roads {
        active, another := trace(path.A), trace(path.B)
        if active == another {
            continue
        }
        sum += path.Weight                              //加入此边

        if -nodes[active].mark < -nodes[another].mark {
            active, another = another, active
        }
        nodes[active].mark += nodes[another].mark       //并少入多

        tail := nodes[active].next                      //两连通域
        nodes[active].next, nodes[another].next = nodes[another].next, tail
        for u := nodes[active].next; u != tail; u = u.next {
            u.mark = active
        }

        if -nodes[active].mark == size { return sum, nil }
    }
    return sum, errors.New("isolated part exist")
}

　　这里记E为边数，V为点数。我们知道，对边排序的复杂度是O(ElogE)，对边遍历的复杂度是O(E)。至于连通操作，其实是O(VlogV)级的。E显然不小于V，故整体的复杂度是O(ElogE)。

我们回来探究一下连通操作的复杂度：

设f(X)为连通操作在最坏情况下的复杂度，A是不大于1/2的系数，则 f(X) = MAX( f(AX) + f((1-A)X) + AX )
若 f(X) = O(XlogX)，有 f(AX) + f((1-A)X) + AX = X(logX + (AlogA + (1-A)log(1-A) + A))
其中，令 B = 1/A >= 2，有 AlogA + (1-A)log(1-A) + A = A((1 - ( logB + (B-1)log(1/(1-A)) )
因 B-1 > 0，1/(1-A) > 1，有 logB + (B-1)log(1/(1-A)) > logB >= 1
进而 AlogA + (1-A)log(1-A) + A <= 0，即有 f(AX) + f((1-A)X) + AX <= XlogX
最后，易归纳得 f(X) = O(XlogX) 有效

既生瑜，何生亮

Kruskal算法在稀疏图上有不错的性能，可惜下一节的Prim算法将会超越它。

Prepare Graph [1000000 vertexes & 15172126 edges]
Kruskal: 2.45385937s
Prim:    662.08132ms

目录　上一节　下一节