最小代价生成树 - 张芷铭的个人博客

在计算机科学和网络设计中，最小代价生成树（Minimum Cost Spanning Tree, MCST）是一个重要概念，它在优化资源配置和降低成本中扮演着关键角色。下面，我们将深入探讨最小代价生成树的定义、应用以及相关算法。

定义

最小代价生成树是指在一个加权无向图中，为了连接图中所有顶点而形成的无环子图（即树），且其所有边的权重之和尽可能小。换句话说，最小代价生成树是图的一个生成树，它包含图中的所有顶点，并且具有最小的边权重总和。

应用

最小代价生成树在多个领域中都有广泛的应用，主要包括：

网络设计：在设计和优化电信网络、计算机网络、水力管网等实体网络时，最小代价生成树可以帮助找到成本最低的布线方案。
城市规划：在规划道路、桥梁建设时，利用最小代价生成树可以最小化建设和维护的成本。
集群分析：在数据挖掘和机器学习中，最小代价生成树被用于分析数据点之间的相似性，帮助识别集群。
图像处理：在图像分割和处理中，最小代价生成树可以帮助识别和分割图像中的对象。

相关算法

构造最小代价生成树的算法主要有两种：普里姆算法（Prim’s Algorithm）和克鲁斯卡尔算法（Kruskal’s Algorithm）。这两个算法各有特点，普里姆算法适用于稠密图，因为它是基于顶点的，而克鲁斯卡尔算法适用于稀疏图，因为它是从边出发的。

普里姆算法

普里姆算法从图中的某一顶点开始，逐步增加新的边和顶点，直到生成树包含了图中的所有顶点。算法步骤如下：

选择任意一个顶点作为起始点。
找到连接已有生成树和图中其他顶点的最小边，并将其添加到生成树中。
重复步骤2，直到所有顶点都被包含在生成树中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import sys

class Graph():
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    def printMST(self, parent):
        print("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

    def minKey(self, key, mstSet):
        min = sys.maxsize

        for v in range(self.V):
            if key[v] < min and mstSet[v] == False:
                min = key[v]
                min_index = v

        return min_index

    def primMST(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[0] = 0
        mstSet = [False] * self.V

        parent[0] = -1

        for cout in range(self.V):
            u = self.minKey(key, mstSet)
            mstSet[u] = True

            for v in range(self.V):
                if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        self.printMST(parent)

# 示例
g = Graph(5)
g.graph = [ [0, 2, 0, 6, 0],
            [2, 0, 3, 8, 5],
            [0, 3, 0, 0, 7],
            [6, 8, 0, 0, 9],
            [0, 5, 7, 9, 0]]

g.primMST()

克鲁斯卡尔算法

克鲁斯卡尔算法是另一种构建最小代价生成树的方法，它不是从顶点开始，而是直接从边开始构建。算法步骤如下：

将图中所有的边按权值从小到大排序。
遍历排序后的边列表，如果当前的边连接的两个顶点在生成树中尚未连通，则添加这条边到生成树中。
重复步骤2，直到生成树中包含了图中的所有顶点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def addEdge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def applyUnion(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskalMST(self):
        result = []
        i, e = 0, 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []
        for node in range(self.V):
            parent.append(node)
            rank.append(0)
        while e < self.V - 1:
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                e = e + 1
                result.append([u, v, w])
                self.applyUnion(parent, rank, x, y)
        for u, v, weight in result:
            print("%d - %d: %d" % (u, v, weight))

# 示例
g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)

g.kruskalMST()

最小代价生成树的算法在实际应用中非常有用，不仅可以帮助解决实际问题，还提供了学习和理解图论和算法设计的绝佳案例。通过这些算法，可以有效地解决资源分配和网络设计等实际问题，实现成本的最小化。

定义

应用

相关算法

普里姆算法

克鲁斯卡尔算法

💬 评论