解决连通性问题的四种算法

算法实现

/** file: 1.1-quick_find.go */
package main

import ...

const N = 10
var id [n]int

func main() {
    reader := bufio.NewReader(os.Stdin)

    // 初始化 id 数组，元素值与结点序号相等
    for i := 0; i < N; i++ {
        id[i] = i
    }

    // 读取命令行输入
    for {
        data,_,_ := reader.ReadLine()
        str := String(data)
        if str == "\n" {
            conTinue
        }
        if str == "#" {
            break
        }

        values := Strings.Split(str," ")
        p,_ := strconv.Atoi(values[0])
        q,_ := strconv.Atoi(values[1])

        if Connected(p,q) {
            fmt.Printf("Already Connected nodes: %d-%d\n",p,q)
            conTinue
        }
        Union(p,q)
    }
}

// 判断整数 p 和 q 的结点是否连通
func Connected(p,q int) bool {
    return id[p] == id[q]
}

// 连通 p-q 结点
func Union(p,q int) {
    pid := id[p]
    qid := id[q]
    // 遍历 id 数组，将所有值为 id[p] 的结点全部替换为 id[q]
    for i := 0; i < N; i++ {
        if id[i] == pid {
            id[i] = qid
        }
    }
    fmt.Printf("Unconnected nodes: %d-%d\n",q)
}

运行效果：能判断 2-9 已存在连通关系

复杂度

快速查找算法在判断 p 和 q 是否连通时，只需判断 id[p]@H_618_16@ 和 id[q]@H_618_16@ 是否相等。但 p 和 q 不连通时会进行合并，每次合并都需要遍历整个数组。特性：查找快、合并慢

/** file: 1.2-quick_union.go */

// p 和 q 有相同的根结点，则是连通的
func Connected(p,q int) bool {
    return getRoot(p) == getRoot(q)
}

// 连通 p-q 结点
func Union(p,q int) {
    pRoot := getRoot(p)
    qRoot := getRoot(q)
    id[pRoot] = qRoot        // q 树的根此时有了父结点（p 树的根），完成合并
    fmt.Printf("Unconnected nodes: %d-%d\n",q)
}


// 获取结点 i 的根结点
func getRoot(i int) int {
    // 没到根结点就继续向上寻找
    for i != id[i] {
        i = id[i]
    }
    return i
}

/**
file: 1.3-weighted_version.go
在快速合并算法的基础上，只需要在合并操作中，将小树合并到大树上即可
*/

var id [n]int
var size [n]int

func main() {
     // 初始化 id 数组，元素值与结点序号相等
    for i := 0; i < N; i++ {
        id[i] = i
        size[i] = i
    } 
      ...
}  

...

// 连通 p-q 结点
func Union(p,q int) {
    pRoot := getRoot(p)
    qRoot := getRoot(q)

    // p 树是大树
    if size[pRoot] < size[qRoot] {
        id[pRoot] = qRoot
        size[qRoot] += size[pRoot]
    } else {
        id[qRoot] = id[pRoot]
        size[pRoot] += size[qRoot]
    }

    id[pRoot] = qRoot // q 树的根此时有了父结点（p 树的根），完成合并
    fmt.Printf("Unconnected nodes: %d-%d\n",q)
}

10-8 8-6 11-9 12-9 9-6 6-3 7-3 3-1 4-1 5-1 1-0 2-0

/**
file: 1.4-path_compression_by_halving.go
改动的代码很少，但很精妙
*/

// 获取结点 i 的根结点
func getRoot(i int) int {
    // 没到根结点就继续向上寻找
    for i != id[i] {
        id[i] = id[id[i]]        // 将结点、结点的父结点不断往上挪动，直到都连接上了根结点
        i = id[i]
    }
    return i
}