6B.md

Prim算法

　　不同于Kruskal算法，Prim算法从点着手。我们把图中的点分成两部分：主集团和外围。然后，不断地从外围挑选最靠近主集团的点，将其纳入主集团中，直至主集团包含所有的点。

平凡实现

我们需要记录点的一些状态信息，包括与主集团中最近的点及与此之间的距离。

type vertex struct {
    idx  int    //本顶点编号
    link int    //关联顶点编号
    dist uint   //与关联顶点间的距离
}

　　最初，我们把所有点都设为不可达，然后由一个点开始逐渐扩大领地。每纳入一个点，更新与之相邻的外围点的信息。在输入为邻接矩阵的时候，算法的复杂度为O(V²)。

func PlainPrim(matrix [][]uint) (uint, error) {
    //...
    memo := make([]vertex, size)
    for i := 0; i < size; i++ {
        memo[i].idx, memo[i].dist = i, math.MaxUint         //初始皆不可达
    }
    memo[size-1].dist = 0

    for last := size - 1; last > 0; last-- {
        best := 0
        for i := 0; i < last; i++ {
            dist := matrix[memo[last].idx][memo[i].idx]
            if dist != 0 && dist < memo[i].dist {
                memo[i].dist = dist                         //更新外围点距离主集团的距离
            } else {
                dist = memo[i].dist
            }
            if dist < memo[best].dist {
                best = i                                    //找出最近的外围点
            }
        }
        if memo[best].dist == math.MaxUint {                //无法连通所有点
            return 0, errors.New("isolated part exist")
        }
        sum += memo[best].dist
        memo[best], memo[last-1] = memo[last-1], memo[best] //将最近的外围点纳入主集团
    }
    return sum, nil
}

堆优化

　　Prim算法实质上在进行一种特殊的宽度优先搜索（当所有边的权重相等时退化成普通的宽度优先搜索），在输入为邻接矩阵的情况下，我们可以使用第六章讨论过的配对堆对算法进行优化：

func Prim(roads [][]graph.Path) (uint, error) {
    //...
    const fakeIdx = -1
    nodes := make([]pheap.NodeG[vertex], size)                  //以数组形式申请节点，方便查找
    for i := 1; i < size; i++ {
        nodes[i].Val = vertex{idx: i, link: fakeIdx, dist: 0}   //初始皆在未在案
    }
    nodes[0].Val = vertex{idx: 0, link: 0, dist: 0}
    hp := pheap.New(nearer)
    hp.Push(&nodes[0])

    var cnt int
    for cnt = 0; !hp.IsEmpty(); cnt++ {
        curr := hp.Pop()
        sum += curr.Val.dist
        idx := curr.Val.idx
        curr.Val.idx = fakeIdx                                  //移出外围，纳入主集团
        for _, path := range roads[idx] {
            peer := &nodes[path.Next]
            if peer.Val.link == fakeIdx {                       //未涉及点，纳入外围
                peer.Val.link = idx
                peer.Val.dist = path.Weight
                hp.Push(peer)
            } else if peer.Val.idx != fakeIdx &&                //外围点
                path.Weight < peer.Val.dist {                   //需要调整
                peer.Val.link = idx                             //更新最近邻
                peer.Val.dist = path.Weight
                hp.FloatUp(peer)
    }   }   }
    if cnt != size { return sum, errors.New("isolated part exist") }
    return sum, nil
}

优化实现存在两重遍历：

• 不断地从堆中弹出元素，等同于对点的遍历；
• 分步遍历所有边，向堆中添加元素，或对堆中的剩余元素进行调整。

由配对堆的特点可知，前者的复杂度为O(VlogV)，后者的复杂度为O(E)。因此，算法整体复杂度为O(VlogV +Ｅ)。

---

目录　上一节　下一节