目录
并查集（Disjoint Set Union, DSU）是一种数据结构，用于处理不相交集合的合并和查询问题。在求图的连通分量时，并查集通过模拟图中连通分量的形成过程来找出所有互不相交的连通子图。
并查集应用
•连通分量计算：图中的极大连通子图
•连通性问题：判断节点间是否存在路径
•最小生成树：选择总权重最小的边连接所有顶点的子图
•网络性分析：在有向图中拓扑排序
•社交网络：分析用户间的关系网络
•图像处理：提取连通区域
并查集优化
•路径压缩：减少查找操作路径长度
•按秩合并：平衡树的高度，减少合并操作时间
•按大小合并：根据集合大小合并
并查集实现
•数组：存储父节点和秩
•哈希表：映射元素和父节点
•树形结构：表示集合和元素间的关系
并查集问题
•高树高度：可能导致性能下降
•大量数据：哈希表性能不佳，树形结构内存消耗大
并查集（Disjoint Set）
•树形数据结构，处理不交集合并和查询问题
•操作：查找（Find）和合并（Union）
•应用：连通性问题、网络分析、社交网络、图像处理
并查集特性
•元素分组：每个元素属于一个集合
•快速查找：元素所属的连通分量
•合并操作：将两个集合合并为一个
并查集操作
•查找（Find）：找到所属连通分量的代表元素
•合并（Union）：将两个集合的代表元素合并
初始化阶段
首先，每个顶点被视为一个单独的连通分量，即每个顶点本身就是一个集合，其父节点指向自己。
接着，遍历图中的每条边。对于每条边，如果它连接的两个顶点属于不同的连通分量，就将这两个连通分量合并为一个新的连通分量。合并操作通常通过路径压缩技术来优化，即将路径上的所有节点直接指向根节点，以减少未来查找操作的时间复杂度。
查询阶段
优化策略
并查集在实际应用中通常采用路径压缩和按秩合并等优化策略，以保持树的高度平衡，避免退化成链表，从而维持高效的查找和合并操作。
通过上述步骤，并查集能够在接近线性时间内解决图的连通分量问题，这使得它成为处理大规模图数据连通性分析的有效工具.
复杂度分析
并查集的实现分析
并查集（Union-Find）数据结构通过路径压缩和按秩合并（或按大小合并）优化，使得其基本操作（查找和合并）的时间复杂度几乎是常数级别。这些操作的渐进时间复杂度为 (O(alpha(n)))，其中 (alpha) 是反阿克曼函数，增长极其缓慢。
- 初始化（
UnionFind(int n)）- 时间复杂度：(O(n))
- 说明：初始化时需要对每个节点进行父节点和大小的设置，遍历一遍数组。
- 查找（
find(int x)）- 时间复杂度：(O(alpha(n)))
- 说明：路径压缩优化使得查找操作的时间复杂度几乎是常数时间，反阿克曼函数 (alpha(n)) 对于所有实际应用中的输入大小 (n) 都可以认为是常数。
- 合并（
unionSets(int p, int q)）- 时间复杂度：(O(alpha(n)))
- 说明：按秩合并或按大小合并使得合并操作也几乎是常数时间，反阿克曼函数 (alpha(n)) 对于所有实际应用中的输入大小 (n) 都可以认为是常数。
- 检查连通性（
connected(int p, int q)）- 时间复杂度：(O(alpha(n)))
- 说明：调用两次
find操作，因此其复杂度也是 (O(alpha(n)))。
- 获取连通分量大小（
getSize(int x)）- 时间复杂度：(O(alpha(n)))
- 说明：调用
find操作来获取根节点，进而获取大小。
- 获取所有连通分量的大小（
getComponentSizes()）- 时间复杂度：(O(n cdot alpha(n)))
- 说明：遍历所有节点并调用
find操作，所以其复杂度为 (O(n cdot alpha(n)))。
空间复杂度
- 初始化（
UnionFind(int n)）- 空间复杂度：(O(n))
- 说明：需要两个数组
parent和size，每个数组的大小为 (n)。
- 所有操作的空间复杂度
- 空间复杂度：(O(n))
- 说明：所有操作都只在上述两个数组上进行操作，没有额外的空间开销。
Python实现
# -*- coding: utf-8 -*-
# 并查集的实现
class UnionFind:
def __init__(self, n):
self.count = n
self.parent = list(range(n))
self.size = [1] * n
self.rank = [0] * n
def union_sets(self, p, q):
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
return
if self.rank[root_p] < self.rank[root_q]:
self.parent[root_p] = root_q
self.size[root_q] += self.size[root_p]
elif self.rank[root_p] > self.rank[root_q]:
self.parent[root_q] = root_p
self.size[root_p] += self.size[root_q]
else:
self.parent[root_p] = root_q
self.rank[root_q] += 1
self.size[root_q] += self.size[root_p]
self.count -= 1
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def connected(self, p, q):
return self.find(p) == self.find(q)
def get_count(self):
return self.count
def get_size(self, x):
root = self.find(x)
return self.size[root]
def get_component_sizes(self):
component_sizes = {}
for i in range(len(self.parent)):
root = self.find(i)
component_sizes[root] = self.size[root]
return component_sizes
# 可视化并查集中的连通分量
def visualize_components(uf, n):
components = {}
for i in range(n):
root = uf.find(i)
if root in components:
components[root].append(i)
else:
components[root] = [i]
color_index = 1
root_to_color = {}
for root, nodes in components.items():
root_to_color[root] = color_index
color_index = (color_index + 1) % 16
if color_index == 0:
color_index = 1
colors = [
"\033[0m", # Reset
"\033[31m", # Red
"\033[32m", # Green
"\033[33m", # Yellow
"\033[34m", # Blue
"\033[35m", # Magenta
"\033[36m", # Cyan
"\033[37m", # White
"\033[91m", # Bright Red
"\033[92m", # Bright Green
"\033[93m", # Bright Yellow
"\033[94m", # Bright Blue
"\033[95m", # Bright Magenta
"\033[96m", # Bright Cyan
"\033[97m" # Bright White
]
for root, nodes in components.items():
color = colors[root_to_color[root]]
print(f"{color}Component with root {root}: {' '.join(map(str, nodes))} {colors[0]}")
# -*- coding: utf-8 -*-
from unionFind import UnionFind, visualize_components
def random_test():
import random
random.seed()
# Test case 1: Basic functionality test
uf1 = UnionFind(10)
assert uf1.connected(0, 0) # 0 and 0 are connected
assert not uf1.connected(0, 1) # 0 and 1 are not connected
uf1.union_sets(0, 1)
assert uf1.connected(0, 1) # 0 and 1 are now connected
assert uf1.get_count() == 9 # 9 connected components remaining
# Test case 2: Multiple merge test
uf2 = UnionFind(10)
for i in range(0, 10, 2):
uf2.union_sets(i, i + 1)
assert uf2.get_count() == 5 # Should have 5 connected components
assert uf2.get_size(0) == 2 # Connected component 0 should have size 2
assert uf2.get_size(1) == 2 # Connected component 1 should have size 2
# Test case 3: Path compression test
uf3 = UnionFind(10)
for i in range(10):
uf3.find(i)
assert uf3.find(0) == 0 # Root of 0 is 0
assert uf3.find(1) == 1 # Root of 1 is 1
# Test case 4: Random test
uf4 = UnionFind(100)
num_operations = 1000 # Number of random operations
for _ in range(num_operations):
p = random.randint(0, 99)
q = random.randint(0, 99)
uf4.union_sets(p, q)
component_sizes = uf4.get_component_sizes()
for size in component_sizes.values():
assert size > 0 # Each connected component should have a size greater than 0
print("All tests passed!")
def find_circle_num(is_connected):
n = len(is_connected)
uf = UnionFind(n)
for i in range(n):
for j in range(i + 1, n):
if is_connected[i][j] == 1:
uf.union_sets(i, j)
visualize_components(uf, n)
return uf.get_count()
def circle_nums_test():
isConnected = [
[1, 1, 0],
[1, 1, 0],
[0, 0, 1]
]
print("Number of circles:", find_circle_num(isConnected))
def test_same_set():
uf = UnionFind(10)
uf.union_sets(1, 2)
uf.union_sets(2, 3)
uf.union_sets(4, 5)
print("1 and 3 are in the same set:", "Yes" if uf.connected(1, 3) else "No")
print("1 and 4 are in the same set:", "Yes" if uf.connected(1, 4) else "No")
print("4 and 5 are in the same set:", "Yes" if uf.connected(4, 5) else "No")
visualize_components(uf, 10)
# unionFind的ut
random_test()
# 测试相邻省份数
circle_nums_test()
# 测试两个数是否存在于同一个集合
test_same_set()
C++实现
UnionFind.h
//
// Created by yuyi.di on 2024/4/30.
//
#pragma once
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
class UnionFind {
private:
int count; // 记录连通分量
vector<int> parent; // 节点 x 的根节点是 parent[x]
vector<int> size; // 用于记录每个连通分量的大小
public:
UnionFind(int n) : count(n), parent(n), size(n, 1) {
// 一开始，每个节点是自己的父节点
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
// 将 p 和 q 连接，如果两个节点被连通，那么则让其中的一个根节点连接到另一个节点的根节点上
void unionSets(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
// 将两颗树合并为一颗
parent[rootP] = rootQ; // parent[rootQ] = rootP 效果是一样的
size[rootQ] += size[rootP]; // 更新根节点的大小
--count; // 两个分量合二为一
}
// 返回某个节点 x 的根节点
int find(int x) {
// 根节点的 parent[x] == x
while (parent[x] != x) {
x = parent[x];
}
return x;
}
// 判断 p 和 q 是否连通: 如果两个节点是连通的，那么他们一定拥有相同的根节点
bool connected(int p, int q) {
return find(p) == find(q);
}
// 返回具体有多少个连通分量
int getCount() const {
return count;
}
// 返回某个连通分量中的节点个数
int getSize(int x) {
int root = find(x);
return size[root];
}
// 返回所有连通分量的大小
unordered_map<int, int> getComponentSizes() {
unordered_map<int, int> componentSizes;
for (int i = 0; i < parent.size(); ++i) {
int root = find(i);
componentSizes[root] = size[root];
}
return componentSizes;
}
};
测试文件
#include <iostream>
#include "UnionFind.h" // 假设 UnionFind 类在 UnionFind.h 中定义
void testUnionFind() {
// 初始化 UnionFind 对象，元素数量为 10
UnionFind uf(10);
// 初始时应该有 10 个连通分量
std::cout << "Initial number of components: " << uf.getCount() << std::endl;
// 合并操作
uf.unionSets(1, 2);
uf.unionSets(2, 3);
uf.unionSets(4, 5);
uf.unionSets(5, 6);
uf.unionSets(7, 8);
uf.unionSets(8, 9);
// 验证连通性
std::cout << "1 and 3 connected: " << (uf.connected(1, 3) ? "Yes" : "No") << std::endl;
std::cout << "4 and 6 connected: " << (uf.connected(4, 6) ? "Yes" : "No") << std::endl;
std::cout << "7 and 9 connected: " << (uf.connected(7, 9) ? "Yes" : "No") << std::endl;
std::cout << "1 and 5 connected: " << (uf.connected(1, 5) ? "Yes" : "No") << std::endl;
// 合并更多操作
uf.unionSets(3, 6); // 将两个已有的集合合并
uf.unionSets(9, 1); // 将两个已有的集合合并
// 再次验证连通性
std::cout << "1 and 6 connected after merging: " << (uf.connected(1, 6) ? "Yes" : "No") << std::endl;
std::cout << "7 and 9 connected after merging: " << (uf.connected(7, 9) ? "Yes" : "No") << std::endl;
// 验证最终的连通分量数
std::cout << "Number of components after merging: " << uf.getCount() << std::endl;
// 打印每个连通分量中的节点个数
auto componentSizes = uf.getComponentSizes();
for (const auto& entry : componentSizes) {
std::cout << "Component root " << entry.first << " has size " << entry.second << std::endl;
}
}
int main() {
testUnionFind();
return 0;
}
输出：
C:\Users\yuyi.di\CLionProjects\untitled2\cmake-build-debug\untitled2.exe
Initial number of components: 10
1 and 3 connected: Yes
4 and 6 connected: Yes
7 and 9 connected: Yes
1 and 5 connected: No
1 and 6 connected after merging: Yes
7 and 9 connected after merging: Yes
Number of components after merging: 2
Component root 6 has size 9
Component root 0 has size 1
Process finished with exit code 0
染色可视化
#include <iostream>
#include <unordered_map>
#include <vector>
#include <map>
#include <iomanip>
#include "UnionFind.h" // 假设 UnionFind 类在 UnionFind.h 中定义
using namespace std;
// 为了实现简单的控制台颜色输出，可以使用 ANSI 转义序列
const string colors[] = {
"\033[0m", // Reset
"\033[31m", // Red
"\033[32m", // Green
"\033[33m", // Yellow
"\033[34m", // Blue
"\033[35m", // Magenta
"\033[36m", // Cyan
"\033[37m", // White
"\033[91m", // Bright Red
"\033[92m", // Bright Green
"\033[93m", // Bright Yellow
"\033[94m", // Bright Blue
"\033[95m", // Bright Magenta
"\033[96m", // Bright Cyan
"\033[97m" // Bright White
};
void visualizeComponents(UnionFind& uf, int n) {
unordered_map<int, vector<int>> components;
// 将每个节点添加到其对应的连通分量中
for (int i = 0; i < n; ++i) {
int root = uf.find(i);
components[root].push_back(i);
}
int colorIndex = 1;
map<int, int> rootToColor;
// 为每个连通分量分配颜色
for (const auto& component : components) {
rootToColor[component.first] = colorIndex;
colorIndex = (colorIndex + 1) % (sizeof(colors) / sizeof(colors[0]));
if (colorIndex == 0) {
colorIndex = 1; // 跳过重置颜色
}
}
// 打印连通分量及其节点
for (const auto& component : components) {
int root = component.first;
int color = rootToColor[root];
cout << colors[color] << "Component with root " << root << ": ";
for (int node : component.second) {
cout << node << " ";
}
cout << colors[0] << endl; // Reset color
}
}
int main() {
// 初始化 UnionFind 对象，元素数量为 10
int n = 10;
UnionFind uf(n);
// 合并操作
uf.unionSets(1, 2);
uf.unionSets(2, 3);
uf.unionSets(4, 5);
uf.unionSets(5, 6);
uf.unionSets(7, 8);
uf.unionSets(8, 9);
uf.unionSets(3, 6);
uf.unionSets(9, 1);
// 可视化连通分量
visualizeComponents(uf, n);
return 0;
}
C:\Users\yuyi.di\CLionProjects\untitled2\cmake-build-debug\untitled2.exe
Component with root 6: 1 2 3 4 5 6 7 8 9
Component with root 0: 0
随机测试
int main() {
srand(time(0)); // 初始化随机数生成器
// 测试用例1：基本功能测试
UnionFind uf1(10);
assert(uf1.connected(0, 0)); // 0和0是连通的
assert(!uf1.connected(0, 1)); // 0和1不连通
uf1.unionSets(0, 1);
assert(uf1.connected(0, 1)); // 0和1现在连通
assert(uf1.getCount() == 9); // 剩余9个连通分量
// 测试用例2：多次合并测试
UnionFind uf2(10);
for (int i = 0; i < 10; i += 2) {
uf2.unionSets(i, i + 1);
}
assert(uf2.getCount() == 5); // 应有5个连通分量
assert(uf2.getSize(0) == 2); // 连通分量0的大小应为2
assert(uf2.getSize(1) == 2); // 连通分量1的大小应为2
// 测试用例3：路径压缩测试
UnionFind uf3(10);
for (int i = 0; i < 10; i++) {
uf3.find(i); // 进行路径压缩
}
assert(uf3.find(0) == 0); // 0的根节点是0
assert(uf3.find(1) == 1); // 1的根节点是1
// 测试用例4：随机测试
UnionFind uf4(100);
int numOperations = 1000; // 随机操作的数量
for (int i = 0; i < numOperations; i++) {
int p = rand() % 100;
int q = rand() % 100;
uf4.unionSets(p, q);
}
unordered_map<int, int> componentSizes = uf4.getComponentSizes();
for (const auto& pair : componentSizes) {
assert(pair.second > 0); // 每个连通分量的大小应大于0
}
cout << "All tests passed!" << endl;
return 0;
}
实现优化
路径压缩
路径压缩用于优化查找操作，使得在查找过程中，将路径上的每个节点直接连接到根节点，减少未来查找操作的路径长度。
我们原先的find实现为：
int find(int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
这段代码并没有实现路径压缩。路径压缩的正确实现应该在递归的查找过程中进行。以下是正确的路径压缩实现：
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
按秩合并
按秩合并用于优化合并操作，通过将秩较小的树连接到秩较大的树上，保持树的高度较小，从而减少未来查找操作的时间。
原先的实现的合并并没有按照大小或者秩大小合并，是统一合并
void unionSets(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
// 将两颗树合并为一颗
parent[rootP] = rootQ; // parent[rootQ] = rootP 效果是一样的
size[rootQ] += size[rootP]; // 更新根节点的大小
--count; // 两个分量合二为一
}
这里我们增加rank 数组用于优化合并操作的效率
初始化 rank 数组
rank 数组在并查集初始化时需要设置为零。每个元素开始时都是一个独立的树，树的高度（秩）为 0。
UnionFind(int n) : count(n), parent(n), rank(n, 0) {
for (int i = 0; i < n; ++i) {
parent[i] = i; // 每个节点的父节点是它自己
}
}
rank(n, 0)：构造函数初始化 rank 数组的每个元素为 0，表示每棵树的初始高度为 0。
更新 rank 数组
更新：在合并两个集合时，rank 数组需要更新。具体来说：
- 如果合并的两个集合的秩不同，将高度较小的树合并到高度较大的树上。
- 如果两个集合的高度相同，将其中一棵树的根节点设置为另一棵树的根节点，并将新根节点的秩增加 1。
// 将 p 和 q 连接，如果两个节点被连通，那么则让其中的一个根节点连接到另一个节点的根节点上
void unionSets(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
// 按秩合并，将秩较小的树连接到秩较大的树上
if (rank[rootP] < rank[rootQ]) {
parent[rootP] = rootQ;
} else if (rank[rootP] > rank[rootQ]) {
parent[rootQ] = rootP;
} else {
parent[rootP] = rootQ;
rank[rootQ]++; // 如果秩相同，将秩增加1
}
--count; // 两个分量合二为一
}
算法问题解决
判断元素是否在同一个集合中
#include <iostream>
#include <unordered_map>
#include <vector>
#include <map>
#include <iomanip>
#include "UnionFind.h" // 假设 UnionFind 类在 UnionFind.h 中定义
#include <unordered_set>
using namespace std;
void testSameSet() {
UnionFind uf(10);
uf.unionSets(1, 2);
uf.unionSets(2, 3);
uf.unionSets(4, 5);
std::cout << "1 and 3 are in the same set: " << (uf.connected(1, 3) ? "Yes" : "No") << std::endl;
std::cout << "1 and 4 are in the same set: " << (uf.connected(1, 4) ? "Yes" : "No") << std::endl;
std::cout << "4 and 5 are in the same set: " << (uf.connected(4, 5) ? "Yes" : "No") << std::endl;
visualizeComponents(uf, 10);
}
int main() {
testSameSet();
return 0;
}
岛屿数量
岛屿数量问题：在一个由 '1'（陆地）和 '0'（水）组成的二维网格中，计算其中的岛屿数量。
遍历二维网格，将相邻的陆地用 unionSets 方法连通，最后计算连通分量的数量来得到岛屿数量
#include <iostream>
#include <unordered_map>
#include <vector>
#include <map>
#include <iomanip>
#include "UnionFind.h" // 假设 UnionFind 类在 UnionFind.h 中定义
#include <unordered_set>
using namespace std;
void testNumIslands(vector<vector<char>>& grid) {
if (grid.empty()) return;
int rows = grid.size();
int cols = grid[0].size();
UnionFind uf(rows * cols);
auto getIndex = [cols](int r, int c) { return r * cols + c; };
// 初始化连通分量并合并相邻的陆地
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (grid[r][c] == '1') {
if (r > 0 && grid[r-1][c] == '1') uf.unionSets(getIndex(r, c), getIndex(r-1, c));
if (c > 0 && grid[r][c-1] == '1') uf.unionSets(getIndex(r, c), getIndex(r, c-1));
if (r < rows - 1 && grid[r+1][c] == '1') uf.unionSets(getIndex(r, c), getIndex(r+1, c));
if (c < cols - 1 && grid[r][c+1] == '1') uf.unionSets(getIndex(r, c), getIndex(r, c+1));
}
}
}
// 计算岛屿数量
unordered_set<int> uniqueIslands;
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (grid[r][c] == '1') {
uniqueIslands.insert(uf.find(getIndex(r, c)));
}
}
}
cout << "Number of islands: " << uniqueIslands.size() << endl;
visualizeComponents(uf, rows * cols);
}
int main() {
vector<vector<char>> grid = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}
};
testNumIslands(grid);
return 0;
}
输出
省份数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
UnionFind uf(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (isConnected[i][j] == 1) {
uf.unionSets(i, j);
}
}
}
return uf.getCount();
}
int main() {
vector<vector<int>> isConnected = {
{1, 1, 0},
{1, 1, 0},
{0, 0, 1}
};
cout << "Number of provinces: " << findCircleNum(isConnected) << endl;
return 0;
}
Kruskal 算法实现最小生成树
Kruskal 算法是一种用于查找加权无向图的最小生成树 (MST) 的贪心算法。它基于边的权重从小到大排序，逐步将边加入生成树，同时避免环的形成。
kruskal(int n, vector<pair<int, pair<int, int>>>& edges): 实现 Kruskal 算法，返回最小生成树的边。- 按权重对边进行排序，遍历每条边并使用
UnionFind判断是否连通，如果不连通则将其加入最小生成树。
// Kruskal 算法实现
vector<pair<int, pair<int, int>>> kruskal(int n, vector<pair<int, pair<int, int>>>& edges) {
// 按权重从小到大排序
std::sort(edges.begin(), edges.end());
UnionFind uf(n);
vector<pair<int, pair<int, int>>> mst; // 存储最小生成树的边
for (const auto& edge : edges) {
int weight = edge.first;
int u = edge.second.first;
int v = edge.second.second;
// 如果 u 和 v 不连通，则加入最小生成树
if (!uf.connected(u, v)) {
uf.unionSets(u, v);
mst.push_back(edge);
}
}
return mst;
}
int main() {
int n = 4; // 节点数
vector<pair<int, pair<int, int>>> edges = {
{1, {0, 1}}, {3, {0, 2}}, {4, {0, 3}}, {2, {1, 2}}, {5, {2, 3}}
};
vector<pair<int, pair<int, int>>> mst = kruskal(n, edges);
cout << "Edges in the Minimum Spanning Tree:" << endl;
for (const auto& edge : mst) {
cout << "Weight: " << edge.first << ", Nodes: (" << edge.second.first << ", " << edge.second.second << ")" << endl;
}
return 0;
}
工程意义
最小生成树
1. 网络设计
网络连接与路由优化
在电信网络、计算机网络和电力网络的设计中，最小生成树算法可以用来构建高效的连接结构。MST 可以帮助确定最小的布线成本，同时确保所有节点都连接在一起，避免了冗余连接。
2. 聚类分析
数据分类与聚类
在数据挖掘和机器学习中，MST 可以用于聚类分析。例如，图像处理中的分割问题和模式识别中的分类问题可以通过 MST 来实现。MST 有助于找出数据点之间的自然连接，形成有意义的聚类。
3. 交通与物流
最优路径规划
在交通网络和物流运输中，MST 可以帮助设计最优路径，减少运输成本和时间。通过计算城市之间的最短连接路径，可以有效优化运输路线，提升效率。
4. 互联网内容分发
CDN 优化
在内容分发网络 (CDN) 中，MST 帮助优化服务器间的连接，以最小化数据传输路径，从而提高内容传输的效率和速度。
7. 项目管理
最小生成树在项目管理中也有应用，例如在项目活动之间构建关键路径，以确定项目完成的最短时间。
示例应用：计算机网络设计
假设有五个办公室需要通过网络互相连接，连接的成本如下图所示：
Office 0 - Office 1: 10
Office 0 - Office 2: 6
Office 1 - Office 2: 5
Office 1 - Office 3: 15
Office 2 - Office 3: 4
Office 2 - Office 4: 8
Office 3 - Office 4: 3
使用 Kruskal 算法计算 MST 后，我们可以得到连接成本最小的网络设计：
Office 3 - Office 4: 3
Office 2 - Office 3: 4
Office 1 - Office 2: 5
Office 0 - Office 2: 6
总成本为 18。这种优化可以大大节省布线成本，提升网络性能。
No comments yet.