最小生成树(Minimum Spanning Tree, MST)问题是图论中的一个重要问题,其核心思想是:给定一个无向加权图(每条边具有权重值),通过选择若干边构建一棵包含所有顶点的生成树,并确保这些边的权重总和最小。最小生成树不仅保持了生成树的连通性和无圈性,还要求总权重最小化。在实际应用中,最小生成树问题在计算机科学和网络设计领域广泛使用,它常用于优化电路网络、建立通信网络、规划道路交通系统等,可以有效降低基础设施建设成本、提高资源利用效率,这类问题可通过经典的算法如Prim和Kruskal进行求解。
无向图 | 最小树 |
---|---|
一、最小树的界定与描述
什么是树?
树是图论中的一种特殊数据结构,是一个无圈、连通的无向图。树由顶点和边组成,满足以下特征:
无圈性:树中没有任何回路,即任意两个顶点之间有且仅有一条路径。
连通性:树是连通的,任意两个顶点之间都有一条路径相连。
什么是生成树?
生成树是指从一个连通无向图中选择若干条边,构成一个包含图中所有顶点且无圈的子图。生成树满足以下条件:
覆盖所有顶点:生成树中的顶点与原图相同,包含原图的所有顶点。
无圈性:生成树中没有任何环,满足树的定义。
边的数量:生成树的边数是\(n-1\),\(n\)是顶点的数量。
对于一个连通图,可能存在多个不同的生成树,每棵生成树都符合上述定义。
图 | 树非生成树 | 生成树或支撑树 |
---|---|---|
树图具有下面重要性质:
设 \(T=(V, E)\) 是一个 \(|V|\geqslant 3\) 的无向图,则下列关于树的命题是等价的:
\(T\) 连通且无圈;
\(T\) 的任何两个顶点间均必有一条且仅有一条通路相连;
\(T\) 连通且有 \(n-1\) 条边,这里 \(n=|V|\);
\(T\) 有 \(n-1\) 条边且无圈,这里 \(n=|V|\);
\(T\) 无圈,但在 \(T\) 中任意两个不相邻的顶点间添加一条边,就可构成一个圈;
\(T\) 连通,但去掉任意一条边后就不连通,即树 \(T\) 是连通且边数最少的图。
什么是最小生成树(最小树)?
最小生成树是生成树的一种特殊形式,定义为:在一个加权无向图中,所有生成树中边权和最小的那棵生成树。它不仅符合生成树的所有条件,还要求所选边的权重总和最小。若\(G=(V, E, W)\) 是一个连通的赋权图,\(T=(V, S)\) 是 \(G\) 的支撑树,把 \(T\) 中所有边的权之和称作树 \(T\) 的权,记作 \(w(T)\),即:$$w(T) = \sum_{e\in S} w(e)$$,\(G\) 中权最小的支撑树 \(T\) 称为 \(G\) 的最小支撑树,简称最小树。
在现实生活中,比如在城市之间建立输电网络、电话线网或光纤网络时,我们希望找到一种最优的布线方案,使得总长度或总费用最小化。这类问题可以被转化为赋权图的最小树问题。
最小生成树具有特点:
连通性:最小生成树依然是连通的,能够覆盖图的所有顶点。
无圈性:最小生成树没有回路,符合树的基本属性。
最小权重和:最小生成树的边权重总和在所有可能的生成树中最小。
最小生成树在网络优化、路径规划、通信设计等领域具有重要应用,常用于降低成本、提高效率。
二、最小树算法Python
最小生成树的求解方法有多种,最经典的两种算法是Prim算法和Kruskal算法。
2.1 kruscal算法
Kruskal算法同样基于贪心思想,但与Prim算法不同的是,它是基于边的排序进行操作的。Kruskal算法先将图中的所有边按权重从小到大排序,然后依次选择这些边,确保选择的边不会形成环。算法适合处理稀疏图。Kruskal算法步骤:
将图中的所有边按权重升序排列。
依次选择权重最小的边,判断该边是否会形成环。如果不会形成环,则将该边加入生成树。
重复步骤2,直到生成树包含 \(n-1\)条边为止。
例1:给定无向图\(G(n,m\)表明图G有\(n\)个顶点,\(m\)条边,通过Kruskal算法构造一个最小生成树。
import networkx as nx
import matplotlib.pyplot as plt
# 设置中文字体,确保Matplotlib支持中文
plt.rcParams['font.sans-serif'] = ['SimHei'] # 设置中文字体为黑体
plt.rcParams['axes.unicode_minus'] = False # 解决负号显示问题
# 创建图
G = nx.Graph()
# 添加节点
nodes = ['V1', 'V2', 'V3', 'V4', 'V5', 'V6']
G.add_nodes_from(nodes)
# 添加边和权重
edges = [
('V1', 'V5', 1),
('V1', 'V6', 2),
('V1', 'V2', 3),
('V2', 'V6', 4),
('V2', 'V3', 5),
('V3', 'V6', 6),
('V3', 'V4', 7),
('V4', 'V6', 8),
('V4', 'V5', 9)
]
G.add_weighted_edges_from(edges)
# Kruskal最小生成树的边
mst_edges = [('V1', 'V5'), ('V1', 'V6'), ('V1', 'V2'), ('V2', 'V3'), ('V3', 'V4')]
# 手动设置每个节点的位置,确保V6在中间,其他顶点围绕它
pos = {
'V6': (0, 0), # V6在中间
'V1': (0, 1), # V1在上方
'V2': (1, 0.5), # V2在右上方
'V3': (1, -0.5), # V3在右下方
'V4': (0, -1), # V4在下方
'V5': (-1, 0) # V5在左侧
}
# 绘制图形
plt.figure(figsize=(8, 6))
# 绘制所有边,调整线条粗细和节点大小,设置节点标签的字体大小为15
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=3000, font_size=45, font_weight='bold', edge_color='gray', width=6) # 字体和边线粗细增加三倍
nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): f'{d}' for u, v, d in edges}, font_size=30) # 边权重的字体大小为默认的三倍
# 用红色标出最小生成树的边,线宽设置为原来的三倍
nx.draw_networkx_edges(G, pos, edgelist=mst_edges, width=6, edge_color='red') # 最小生成树的边线宽度为原来的三倍
# 设置标题,字体大小增大三倍
plt.title("最小生成树", fontsize=60)
# 显示图形
plt.show()
2.2 Prim算法
Prim算法是一种基于贪心思想的算法,适合处理稠密图。算法从一个起始顶点开始,将其加入生成树,然后不断选择与当前生成树相连的权重最小的边,将该边所连接的顶点加入生成树,直到所有顶点都被包括在内为止。Prim算法步骤:
从任意一个顶点出发,初始时将该顶点加入生成树。
查找与已加入生成树的顶点相邻的最小权重边,将该边及其相邻的顶点加入生成树。
重复上述步骤,直到所有顶点都包含在生成树中。
例2:某地的5个城镇需要铺设天然气管道,下图中给出了5个城镇之间可以铺设管道的情况的以及距离,先求一个设计方案,用最短的管道将5个城镇连接起来。
原图 | 迭代1 | 迭代5 |
---|---|---|
import networkx as nx
import matplotlib.pyplot as plt
import heapq
# 设置中文字体,确保Matplotlib支持中文
plt.rcParams['font.sans-serif'] = ['SimHei'] # 设置中文字体为黑体
plt.rcParams['axes.unicode_minus'] = False # 解决负号显示问题
# 创建图
G = nx.Graph()
# 添加节点
nodes = ['V1', 'V2', 'V3', 'V4', 'V5', 'V6']
G.add_nodes_from(nodes)
# 添加边和权重
edges = [
('V1', 'V2', 1),
('V1', 'V4', 7),
('V1', 'V3', 3),
('V1', 'V5', 9),
('V2', 'V3', 6),
('V2', 'V4', 4),
('V2', 'V5', 3),
('V3', 'V4', 5),
('V3', 'V6', 10),
('V4', 'V5', 8),
('V4', 'V6', 3)
]
G.add_weighted_edges_from(edges)
# 修改邻接表,基于edges
graph = {
'V1': {'V2': 1, 'V3': 3, 'V4': 7, 'V5': 9},
'V2': {'V1': 1, 'V3': 6, 'V4': 4, 'V5': 3},
'V3': {'V1': 3, 'V2': 6, 'V4': 5, 'V6': 10},
'V4': {'V1': 7, 'V2': 4, 'V3': 5, 'V5': 8, 'V6': 3},
'V5': {'V1': 9, 'V2': 3, 'V4': 8},
'V6': {'V3': 10, 'V4': 3}
}
# Prim算法实现
def prim_mst(graph, start):
mst = [] # 存储最小生成树的边
visited = set([start]) # 记录已经访问过的节点
edges = [(weight, start, to) for to, weight in graph[start].items()]
heapq.heapify(edges) # 将边加入优先队列
while edges:
weight, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst.append((frm, to))
for next_to, next_weight in graph[to].items():
if next_to not in visited:
heapq.heappush(edges, (next_weight, to, next_to))
return mst
# 使用Prim算法求最小生成树
mst_edges = prim_mst(graph, 'V1')
# 定义节点的位置布局,V3在中间
pos = {
'V3': (0, 0), # V3在中间
'V1': (0, 1), # V1在上方
'V2': (1, 0.5), # V2在右上方
'V4': (0, -1), # V4在下方
'V5': (-1, 0), # V5在左侧
'V6': (1, -0.5) # V6在右下方
}
# 调整字体大小和边线粗细
plt.figure(figsize=(8, 6))
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=3000, font_size=36, font_weight='bold', edge_color='gray', width=6) # 调整font_size和width
nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): f'{d}' for u, v, d in edges}, font_size=30) # 边权重的字体大小调大
# 用红色标出最小生成树的边
nx.draw_networkx_edges(G, pos, edgelist=mst_edges, width=6, edge_color='red') # 边线粗三倍
# 设置标题
plt.title("Prim算法求解最小生成树", fontsize=36) # 标题字体调整
# 显示图形
plt.show()
总结
最小生成树问题是图论中重要的优化问题,它要求在给定的无向图中找到一棵边权和最小的生成树。生成树具有连通性和无环性,而最小生成树则在此基础上还要求边的权重和最小。通过Prim算法和Kruskal算法,我们可以高效地解决最小生成树问题。Prim算法适用于稠密图,而Kruskal算法则更适合稀疏图。在实际应用中,最小生成树被广泛用于网络设计、通信系统规划、输电线路布局等领域。在实际工程中,最小生成树的求解不仅能降低系统的成本,还能提高资源的利用效率。通过使用适当的算法和数据结构,我们能够快速且准确地求解最小生成树问题。