【图论】最小生成树

**图论中的最小生成树**

在图论中，最小生成树是指一个连通图的边集，且其权值之和最小。最小生成树是图论中一个非常重要的概念，它们广泛应用于网络设计、计算机科学等领域。

**什么是最小生成树？**

最小生成树是指一个连通图的边集，且其权值之和最小。换句话说，最小生成树是指从图中的任意两个顶点到达其他所有顶点所需的最短路径集合。

**最小生成树的性质**

1. **连通性**: 最小生成树一定是连通的，因为它包含了从任意两个顶点到达其他所有顶点所需的最短路径。
2. **最小权值**: 最小生成树的边集中的每条边都是必要的，因为如果去掉其中任何一条边，图就不再连通。

**最小生成树的算法**

有多种算法可以求得最小生成树，其中包括：

1. **Prim算法**
2. **Kruskal算法**
3. **Dijkstra算法**

### Prim算法Prim算法是最早提出的最小生成树算法，它基于以下思想：从图中选择一个顶点作为起始点，然后逐步添加边，直到所有顶点都被连接起来。

**代码示例（Python）**

import networkx as nxdef prim(graph):
 #选择一个随机顶点作为起始点 start_node = list(graph.nodes)[0]
 # 初始化最小生成树 mst = nx.Graph()
 # 将起始点添加到最小生成树中 mst.add_node(start_node)
 # 初始化已访问的顶点集合 visited = set([start_node])
 while len(visited) < graph.number_of_nodes():
 # 找到当前顶点的邻居中权值最小的边 min_edge = None for neighbor in graph.neighbors(start_node):
 if neighbor not in visited:
 edge = (start_node, neighbor)
 if min_edge is None or graph.get_edge_data(*edge)['weight'] < graph.get_edge_data(*min_edge)['weight']:
 min_edge = edge # 将最小边添加到最小生成树中 mst.add_edge(*min_edge)
 # 将邻居顶点标记为已访问 visited.add(min_edge[1])
 # 更新起始点 start_node = min_edge[1]
 return mst# 示例图G = nx.Graph()
G.add_edge('A', 'B', weight=2)
G.add_edge('A', 'C', weight=3)
G.add_edge('B', 'D', weight=4)
G.add_edge('C', 'D', weight=1)

print(prim(G))

import networkx as nxdef kruskal(graph):
 # 将所有边按权值从小到大排序 edges = sorted(graph.edges(data=True), key=lambda x: x[2]['weight'])
 # 初始化最小生成树 mst = nx.Graph()
 # 初始化已访问的顶点集合 visited = set()
 for edge in edges:
 # 如果边连接了两个未访问过的顶点，则添加到最小生成树中 if edge[0] not in visited or edge[1] not in visited:
 mst.add_edge(*edge[:2])
 visited.update([edge[0], edge[1]])
 return mst# 示例图G = nx.Graph()
G.add_edge('A', 'B', weight=2)
G.add_edge('A', 'C', weight=3)
G.add_edge('B', 'D', weight=4)
G.add_edge('C', 'D', weight=1)

print(kruskal(G))

import networkx as nxdef dijkstra(graph):
 # 初始化距离和前驱顶点 distance = {node: float('inf') for node in graph.nodes}
 predecessor = {node: None for node in graph.nodes}
 # 将起始点标记为已访问 start_node = list(graph.nodes)[0]
 distance[start_node] =0 # 初始化未访问的顶点集合 unvisited = set([start_node])
 while unvisited:
 # 找到当前顶点中距离最小的邻居 min_node = None for node in unvisited:
 if min_node is None or distance[node] < distance[min_node]:
 min_node = node # 更新距离和前驱顶点 for neighbor in graph.neighbors(min_node):
 new_distance = distance[min_node] + graph.get_edge_data(min_node, neighbor)['weight']
 if new_distance < distance[neighbor]:
 distance[neighbor] = new_distance predecessor[neighbor] = min_node # 将当前顶点标记为已访问 unvisited.remove(min_node)
 return distance, predecessor# 示例图G = nx.Graph()
G.add_edge('A', 'B', weight=2)
G.add_edge('A', 'C', weight=3)
G.add_edge('B', 'D', weight=4)
G.add_edge('C', 'D', weight=1)

distance, predecessor = dijkstra(G)
print(distance)
print(predecessor)