Kruskal 算法与 Prim 算法

1
// 边的数据结构
2
data class Edge(val from: Int, val to: Int, val weight: Int)
3

4
// 并查集：用于判断环、合并集合
5
class UnionFind(size: Int) {
6
    private val parent = IntArray(size) { it }
7

8
    // 查找根节点，并路径压缩
9
    fun find(x: Int): Int {
10
        if (parent[x] != x) {
11
            parent[x] = find(parent[x])
12
        }
13
        return parent[x]
14
    }
15

16
    // 合并两个集合，若已经连通返回 false
17
    fun union(x: Int, y: Int): Boolean {
18
        val rootX = find(x)
19
        val rootY = find(y)
20
        if (rootX == rootY) return false
21
        parent[rootY] = rootX
22
        return true
23
    }
24
}
25

26
// Kruskal 算法：从邻接矩阵生成边集合并构建最小生成树
27
fun kruskalFromAdjMatrix(adjMatrix: Array<IntArray>): List<Edge> {
28
    val nodeCount = adjMatrix.size
29
    val edges = extractEdgesFromMatrix(adjMatrix)
30

31
    if (edges.isEmpty()) {
32
        throw IllegalArgumentException("图中没有有效的边")
33
    }
34

35
    return kruskal(nodeCount, edges)
36
}
37

38
// 辅助函数：从邻接矩阵中提取边（避免重复）
39
fun extractEdgesFromMatrix(matrix: Array<IntArray>): List<Edge> {
40
    val edges = mutableListOf<Edge>()
41
    val n = matrix.size
42

43
    for (i in 0 ..< n) {
44
        for (j in i + 1 ..< n) {
45
            val w = matrix[i][j]
46
            if (w != 0 && w != Int.MAX_VALUE) {
47
                edges.add(Edge(i, j, w))
48
            }
49
        }
50
    }
51

52
    return edges
53
}
54

55
// Kruskal 主体：边排序 + 并查集连接
56
fun kruskal(nodeCount: Int, edges: List<Edge>): List<Edge> {
57
    val mst = mutableListOf<Edge>()
58
    val uf = UnionFind(nodeCount)
59

60
    for (edge in edges.sortedBy { it.weight }) {
61
        if (uf.union(edge.from, edge.to)) {
62
            mst.add(edge)
63
            if (mst.size == nodeCount - 1) break
64
        }
65
    }
66

67
    return mst
68
}

1
fun main() {
2
    val INF = Int.MAX_VALUE
3
    val adjMatrix = arrayOf(
4
        intArrayOf(0,  7, INF,  5, INF, INF, INF), // A
5
        intArrayOf(7,  0,  8,  9,  7, INF, INF),   // B
6
        intArrayOf(INF, 8,  0, INF, 5, INF, INF),  // C
7
        intArrayOf(5,  9, INF,  0, 15, 6, INF),    // D
8
        intArrayOf(INF, 7, 5, 15,  0, 8,  9),      // E
9
        intArrayOf(INF, INF, INF, 6, 8,  0, 11),   // F
10
        intArrayOf(INF, INF, INF, INF, 9, 11, 0)   // G
11
    )
12

13
    val mst = kruskalFromAdjMatrix(adjMatrix)
14
    val cityNames = listOf("A", "B", "C", "D", "E", "F", "G")
15

16
    println("最小花费的高铁修建方案如下：")
17
    var totalCost = 0
18
    for (edge in mst) {
19
        println("${cityNames[edge.from]} -- ${cityNames[edge.to]} : 费用 ${edge.weight}")
20
        totalCost += edge.weight
21
    }
22
    println("总花费：$totalCost")
23
}

1
fun prim(adjMatrix: Array<IntArray>): List<Triple<Int, Int, Int>> {
2
    val n = adjMatrix.size
3
    val visited = BooleanArray(n) { false }      // 记录已加入 MST 的点
4
    val minDist = IntArray(n) { Int.MAX_VALUE }  // 每个点到 MST 的最小距离
5
    val parent = IntArray(n) { -1 }              // 每个点在 MST 中的父节点
6

7
    minDist[0] = 0
8

9
    for (i in 0 ..< n) {
10
        // 选出未加入 MST 中、距离最小的点
11
        var u = -1
12
        var min = Int.MAX_VALUE
13
        for (j in 0 ..< n) {
14
            if (!visited[j] && minDist[j] < min) {
15
                min = minDist[j]
16
                u = j
17
            }
18
        }
19

20
        if (u == -1) break // 图不连通
21

22
        visited[u] = true
23

24
        // 用 u 点更新其他相邻点的最小距离
25
        for (v in 0 ..< n) {
26
            val weight = adjMatrix[u][v]
27
            if (!visited[v] && weight != 0 && weight < minDist[v]) {
28
                minDist[v] = weight
29
                parent[v] = u
30
            }
31
        }
32
    }
33

34
    // 构建结果
35
    val result = mutableListOf<Triple<Int, Int, Int>>()
36
    for (v in 1 ..< n) {
37
        val u = parent[v]
38
        if (u != -1) {
39
            result.add(Triple(u, v, adjMatrix[u][v]))
40
        }
41
    }
42

43
    return result
44
}

1
fun main() {
2
    val INF = Int.MAX_VALUE
3
    val adjMatrix = arrayOf(
4
        intArrayOf(0,  7, INF,  5, INF, INF, INF),
5
        intArrayOf(7,  0,  8,  9,  7, INF, INF),
6
        intArrayOf(INF, 8,  0, INF, 5, INF, INF),
7
        intArrayOf(5,  9, INF,  0, 15, 6, INF),
8
        intArrayOf(INF, 7, 5, 15,  0, 8,  9),
9
        intArrayOf(INF, INF, INF, 6, 8,  0, 11),
10
        intArrayOf(INF, INF, INF, INF, 9, 11, 0)
11
    )
12

13
    val cityNames = listOf("A", "B", "C", "D", "E", "F", "G")
14
    val mst = prim(adjMatrix)
15

16
    println("最小花费的高铁修建方案如下：")
17
    var totalCost = 0
18
    for ((u, v, w) in mst) {
19
        println("${cityNames[u]} -- ${cityNames[v]} : 费用 $w")
20
        totalCost += w
21
    }
22
    println("总花费：$totalCost")
23
}