数据结构 —— 最小生成树

作者：在线问答5 | 2024-07-14 15:41:07

踩

数据结构 —— 最小生成树

什么是最小生成树
Kruskal算法
Prim算法

今天我们来看一下最小生成树：

我们之前学习的遍历算法并没有考虑权值，仅仅就是遍历结点：
在这里插入图片描述今天的最小生成树要满足几个条件：

考虑权值
所有结点联通
权值之和最小
无环

在这里插入图片描述

什么是最小生成树

最小生成树（Minimum Spanning Tree，简称MST）是指在一个加权的、无向的连通图中，由所有顶点构成的一个子图，这个子图是一棵树，并且其所有边的权重之和最小。换句话说，最小生成树是在保证图中所有顶点连通的前提下，使得连接这些顶点的边的总成本最低的一棵树。

最小生成树具有以下特性：

它包含图中的所有顶点。
它是一个没有环的连通子图（即树）。
它的边数比顶点数少一（对于 n 个顶点的图，有 n-1 条边）。
它的边的总权重是所有可能生成树中最小的。

最小生成树在很多实际应用中都有重要作用，例如在设计电信网络时，为了连接多个地点而需要铺设电缆或光纤，最小生成树可以用来确定一种成本最低的铺设方案。

求解最小生成树的常用算法包括：

Kruskal算法：此算法通过不断选择权重最小的边来构建最小生成树，同时避免添加会导致环路形成的边。它通常利用并查集（Disjoint Set Union）数据结构来检测环路。
Prim算法：此算法从任意一个顶点开始，逐步将顶点及其权重最小的连接边加入到生成树中，直到所有顶点都被包含进来。Prim算法可以使用优先队列（Priority Queue）来高效地选择下一个应加入的边。

我们今天就来介绍一下这两种算法：

Kruskal算法

Kruskal算法，简单来说，就是把所有边拿出来，从小到大挑边，构成最小生成树：

Kruskal算法是一种用于寻找加权、无向连通图的最小生成树（Minimum Spanning Tree, MST）的贪心算法。它的核心思想是在不形成任何环路的情况下，选择权重最小的边来构建生成树，直到所有的顶点都被包含在树中。

以下是Kruskal算法的主要步骤：

排序边：将图中所有的边按照权重从小到大排序。
初始化森林：创建一个森林，其中每个顶点都是一个单独的树（即每个顶点都是一个独立的连通分量）。
选择边：遍历排序后的边列表。对于每条边，检查它的两个端点是否已经在同一棵树中（即是否属于同一个连通分量）。如果不是，将这条边添加到最小生成树中，并将这两个顶点所在的树合并成一棵更大的树。
重复步骤3：继续选择满足条件的边，直到最小生成树中包含了图中的所有顶点，或者已经选择了n-1条边（其中n是顶点的数量）。

在这里插入图片描述

Kruskal算法的关键在于能够快速地检测边的两个端点是否属于同一棵树，这通常是通过使用并查集（Union-Find）数据结构来实现的。并查集允许我们在对数时间内执行“查找”操作（确定顶点所属的树）和“合并”操作（将两棵树合并成一棵树）。

// 使用Kruskal算法计算最小生成树的总权重
W Kruskal(Self& minTree) // Self应为当前类的引用，minTree是用于存储最小生成树的实例
{
    // 初始化最小生成树的顶点集和索引
    minTree._vertex = _vertex;
    minTree._index = _index;
    minTree._matrix.resize(_vertex.size()); // 创建一个邻接矩阵，用于存储最小生成树中的边的权重

    for (auto& e : minTree._matrix) // 将邻接矩阵的所有元素初始化为最大权重值MAX_W
    {
        e.resize(_vertex.size(), MAX_W);
    }

    // 创建一个优先级队列，用于存储边的信息
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;

    // 将所有边（除了自环和重复边）加入优先级队列
    for (size_t i = 0; i < _vertex.size(); i++) 
    {
        for (size_t j = 0; j < _vertex.size(); j++) 
        {
            if (i < j && _matrix[i][j] != MAX_W) // 确保不加入自环和重复边
            {
                pq.push(Edge(i, j, _matrix[i][j])); // 将边加入优先级队列
            }
        }
    }

    // 初始化变量，用于记录最小生成树的总权重和边的数量
    W total = W();
    int size = 0;

    UnionFindSet ufs(_vertex.size()); // 创建并查集，用于判断顶点是否已经连接

    while (!pq.empty()) // 当优先级队列非空时
    {
        Edge min = pq.top(); // 取出权重最小的边
        pq.pop(); // 移除已取出的边

        // 判断边的两个顶点是否已经在同一集合内（即是否已经连接）
        if (!ufs.InSet(min._srci, min._desi)) 
        {
            cout << _vertex[min._srci] << "-" << _vertex[min._desi] << ":" << _matrix[min._srci][min._desi] << endl; // 打印边的信息

            minTree._AddEdge(min._srci, min._desi, min._w); // 将边加入最小生成树
            total += min._w; // 更新最小生成树的总权重

            ufs.Union(min._srci, min._desi); // 合并两个顶点所在的集合
            ++size; // 增加边的数量
        }
    }

    cout << endl;

    minTree.Print(); // 打印最小生成树

    // 如果边的数量等于顶点数量减一，则返回最小生成树的总权重
    if (size == _vertex.size() - 1)
    {
        return total;
    }
    else
    {
        return W(); // 否则返回默认权重值（可能表示无法形成最小生成树）
    }
}
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
55
56
57
58
59
60
61
62
63
64
65
66

我们可以来测试一下：

	void TestGraph2()
	{
		string a[] = {"海皇","高斯","小傲","小潮","胖迪","小杨","皖皖"};
		Graph<string, int,INT_MAX, false> g1(a, sizeof(a)/sizeof(a[0]));
		g1.AddEdge("小潮", "小傲", 30);
		g1.AddEdge("小潮", "高斯", 83);
		g1.AddEdge("小潮", "海皇", 34);
		g1.AddEdge("胖迪", "海皇", 78);
		g1.AddEdge("胖迪", "小傲", 76);
		g1.AddEdge("小杨", "皖皖", 54);
		g1.AddEdge("小杨", "高斯", 48);

		g1.Print();
		cout << endl;

		Graph<string, int, INT_MAX, false> kminTree;
		cout << "Kruskal:" << g1.Kruskal(kminTree) << endl;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在这里插入图片描述按照Kruskal算法，构建出来的图是这样的：
胖迪和海皇的关系被抹除了，其实我们之前的图里有环：

Kruskal算法的时间复杂度主要取决于排序边的操作和并查集的效率。在最好的情况下，排序边的时间复杂度为O(E log E)，其中E是边的数量；并查集操作的时间复杂度接近常数，因此整个算法的时间复杂度近似为O(E log E)。由于排序的主导作用，该算法适用于边的数量远小于顶点数量平方的图，即稀疏图。

Prim算法

Prim算法和上面的思想差不多，但是，Prim算法会从一个顶点开始，这里我假设是从"小潮"开始：
在这里插入图片描述
跟小潮连接的3条边，会进入优先级队列，维护起来：
接下来，会选择30的权重来构造，然后30这条边的另一边的小傲的边入优先级队列：

以此类推：

// 使用Prim算法构建并返回最小生成树的总权重
W Prim(Self& minTree, const V& vertex) // Self应该是当前类的引用，minTree是用于存储最小生成树的实例，vertex是顶点的容器
{
    // 初始化最小生成树的顶点集和索引
    minTree._vertex = _vertex;
    minTree._index = _index;
    minTree._matrix.resize(_vertex.size()); // 创建一个邻接矩阵，用于存储最小生成树中的边的权重

    // 初始化邻接矩阵的所有元素为最大权重值MAX_W
    for (auto& e : minTree._matrix)
    {
        e.resize(_vertex.size(), MAX_W);
    }

    // 区分顶点集合：已选择和未选择
    size_t srcIndex = FindSrci(vertex); // 找到起始顶点的索引
    vector<bool> select(_vertex.size(), false); // 已选择顶点集合，初始时所有顶点都未选择
    vector<bool> non_select(_vertex.size(), true); // 未选择顶点集合，初始时所有顶点都未被选择

    select[srcIndex] = true; // 起始顶点被标记为已选择
    non_select[srcIndex] = false; // 起始顶点从未选择集合中移除

    // 创建一个优先级队列，用于存储待处理的边
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq; // 边按权重从小到大排序

    // 将起始顶点的邻接边加入优先级队列
    for (int i = 0; i < _vertex.size(); i++)
    {
        if (_matrix[srcIndex][i] != MAX_W) // 如果存在边，且不是最大权重（表示边存在）
        {
            pq.push(Edge(srcIndex, i, _matrix[srcIndex][i])); // 加入边信息到优先级队列
        }
    }

    // 初始化计数器和总权重
    size_t size = 0;
    W total = W(); // 初始化总权重为0

    // 当优先级队列非空时
    while (!pq.empty())
    {
        Edge min = pq.top(); // 获取当前权重最小的边
        pq.pop(); // 从队列中移除已处理的边

        // 如果目标顶点已被选择，跳过这条边
        if (select[min._desi]) continue;

        // 输出边的信息
        cout << _vertex[min._srci] << "-" << _vertex[min._desi] << ":" << _matrix[min._srci][min._desi] << endl;

        // 添加边到最小生成树
        minTree._AddEdge(min._srci, min._desi, min._w);

        // 标记目标顶点为已选择
        select[min._desi] = true;
        non_select[min._desi] = false;
        ++size; // 已处理的边数量加1
        total += min._w; // 更新总权重

        // 将新加入顶点的邻接边加入优先级队列
        for (size_t i = 0; i < _vertex.size(); i++)
        {
            if (_matrix[min._desi][i] != MAX_W && non_select[i]) // 如果存在边且目标顶点未被选择
            {
                pq.push(Edge(min._desi, i, _matrix[min._desi][i])); // 加入边信息到优先级队列
            }
        }
    }

    // 打印最小生成树
    minTree.Print();

    // 如果边的数量等于顶点数量减一，则返回最小生成树的总权重
    if (size == _vertex.size() - 1)
    {
        return total;
    }
    else
    {
        return W(); // 否则返回默认权重值（可能表示无法形成最小生成树）
    }
}
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

	void TestGraph2()
	{
		string a[] = {"海皇","高斯","小傲","小潮","胖迪","小杨","皖皖"};
		Graph<string, int,INT_MAX, false> g1(a, sizeof(a)/sizeof(a[0]));
		g1.AddEdge("小潮", "小傲", 30);
		g1.AddEdge("小潮", "高斯", 83);
		g1.AddEdge("小潮", "海皇", 34);
		g1.AddEdge("胖迪", "海皇", 78);
		g1.AddEdge("胖迪", "小傲", 76);
		g1.AddEdge("小杨", "皖皖", 54);
		g1.AddEdge("小杨", "高斯", 48);

		g1.Print();
		cout << endl;

		Graph<string, int, INT_MAX, false> kminTree;
		cout << "Kruskal:" << g1.Kruskal(kminTree) << endl;

		cout << endl;

		Graph<string, int, INT_MAX, false> pminTree;
		cout << "Prim:" << g1.Prim(pminTree,"小潮") << endl;

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

在这里插入图片描述

Prim算法同样是用于寻找加权无向图的最小生成树(Minimum Spanning Tree, MST)的一种贪心算法。与Kruskal算法不同的是，Prim算法从一个顶点开始，逐步添加最短的边来扩展树，直到包含所有的顶点。

Prim算法基本步骤：

选择任意一个顶点作为起始顶点。
在当前树的顶点的邻接边中找到权重最小的边，将这条边添加到树中，并将新的顶点也添加进来。
重复步骤2，直到树包含所有的顶点。

这是两种算法挑选边的过程和最后结果，大家可以类比对比：

		//Kruskal算法
		W Kruskal(Self& minTree)
		{
			//初始化
			minTree._vertex = _vertex;
			minTree._index = _index;
			minTree._matrix.resize(_vertex.size());

			for (auto& e : minTree._matrix)
			{
				e.resize(_vertex.size(), MAX_W);
			}

			//优先级队列
			priority_queue<Edge, vector<Edge>, greater<Edge>> pq;

			for (size_t i = 0; i < _vertex.size(); i++)
			{
				for (size_t j = 0; j < _vertex.size(); j++)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						pq.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}

			//拿边构造最小生成树
			W totoal = W();
			int size = 0;
			UnionFindSet ufs(_vertex.size());

			while (!pq.empty())
			{
				Edge min = pq.top();
				//出边
				pq.pop();

				//判断是否在同一集合
				if (!ufs.InSet(min._srci ,min._desi))
				{
					cout << _vertex[min._srci] << "-" << _vertex[min._desi] <<
						":" << _matrix[min._srci][min._desi] << endl;

					minTree._AddEdge(min._srci, min._desi, min._w);
					totoal += min._w;

					//合并
					ufs.Union(min._srci, min._desi);
					++size;
				}
			}

			cout << endl;

			minTree.Print();

			if (size == _vertex.size() - 1)
			{
				return totoal;
			}
			else
			{
				return W();
			}

			
		}

		W Prim(Self& minTree,const V& vertex)
		{
			//初始化
			minTree._vertex = _vertex;
			minTree._index = _index;
			minTree._matrix.resize(_vertex.size());

			for (auto& e : minTree._matrix)
			{
				e.resize(_vertex.size(), MAX_W);
			}

			//区分集合
			size_t srcIndex = FindSrci(vertex);
			vector<bool> select(_vertex.size(), false);
			vector<bool> non_select(_vertex.size(), true);

			select[srcIndex] = true;
			non_select[srcIndex] = false;

			//开始入边
			priority_queue<Edge, vector<Edge>, greater<Edge>> pq;

			for (int i = 0; i < _vertex.size(); i++)
			{
				if (_matrix[srcIndex][i] != MAX_W)
				{
					pq.push(Edge(srcIndex, i, _matrix[srcIndex][i]));
				}
			}

			size_t size = 0;
			W totoal = W();

			while (!pq.empty())
			{
				Edge min = pq.top();
				pq.pop();

				if (select[min._desi])
					continue;

				cout << _vertex[min._srci] << "-" << _vertex[min._desi] <<
					":" << _matrix[min._srci][min._desi] << endl;

				minTree._AddEdge(min._srci, min._desi, min._w);

				select[min._desi] = true;
				non_select[min._desi] = false;
				++size;
				totoal += min._w;

				//新入的顶点的边也加入到优先级队列
				for (size_t i = 0; i < _vertex.size(); i++)
				{
					if (_matrix[min._desi][i] != MAX_W && non_select[i])
					{
						pq.push(Edge(min._desi, i, _matrix[min._desi][i]));
					}
				}
			}

			minTree.Print();

			if (size == _vertex.size() - 1)
			{
				return totoal;
			}
			else
			{
				return W();
			}

		}
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/825358