4.1 KiB
4.1 KiB
以下是实验报告框架和 Python 实现的模板，供参考：
实验报告：最小生成树
学号：XXXXXX
姓名：XXXXXX
一、最小生成树基本思想
最小生成树（Minimum Spanning Tree, MST）是一个无向连通图的一个子图，满足以下条件：
- 是连通图；
- 包含图中所有顶点，但只包含
n-1条边（其中n为顶点数）； - 所有边的权值之和最小。
常用的算法包括：
- Prim算法：逐步扩展生成树，通过选择权值最小的边加入生成树。
- Kruskal算法：先按权值对边排序，再通过判断是否形成环来选择边加入生成树。
二、源码
以下代码实现了 Prim 和 Kruskal 两种算法：
import heapq
# 图的表示方式
class Graph:
def __init__(self, vertices):
self.V = vertices # 顶点数
self.graph = [] # 存储边的列表
def add_edge(self, u, v, weight):
self.graph.append([u, v, weight])
# Prim 算法
def prim_mst(self):
mst_set = [False] * self.V
edge_heap = [(0, 0)] # (权值, 顶点)
total_cost = 0
mst_edges = []
while edge_heap:
weight, u = heapq.heappop(edge_heap)
if mst_set[u]:
continue
mst_set[u] = True
total_cost += weight
for v, w in self._adjacent_edges(u):
if not mst_set[v]:
heapq.heappush(edge_heap, (w, v))
mst_edges.append((u, v, w))
return total_cost, mst_edges
def _adjacent_edges(self, u):
return [(v, weight) for (u_, v, weight) in self.graph if u_ == u] + \
[(u, weight) for (u, v_, weight) in self.graph if v_ == u]
# Kruskal 算法
def kruskal_mst(self):
self.graph.sort(key=lambda x: x[2]) # 按权值排序
parent = list(range(self.V))
rank = [0] * self.V
def find(u):
if parent[u] != u:
parent[u] = find(parent[u])
return parent[u]
def union(u, v):
root_u = find(u)
root_v = find(v)
if rank[root_u] > rank[root_v]:
parent[root_v] = root_u
elif rank[root_u] < rank[root_v]:
parent[root_u] = root_v
else:
parent[root_v] = root_u
rank[root_u] += 1
mst_edges = []
total_cost = 0
for u, v, weight in self.graph:
if find(u) != find(v):
union(u, v)
mst_edges.append((u, v, weight))
total_cost += weight
return total_cost, mst_edges
# 测试代码
if __name__ == "__main__":
g = Graph(5) # 创建一个包含5个顶点的图
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 6)
g.add_edge(1, 3, 8)
g.add_edge(1, 2, 3)
g.add_edge(1, 4, 5)
g.add_edge(2, 4, 7)
g.add_edge(3, 4, 9)
print("Prim 算法结果:")
cost, edges = g.prim_mst()
print(f"总权值: {cost}, 边: {edges}")
print("\nKruskal 算法结果:")
cost, edges = g.kruskal_mst()
print(f"总权值: {cost}, 边: {edges}")
三、算法分析
-
Prim算法
- 时间复杂度：( O(V^2) )（邻接矩阵实现）或 ( O(E \log V) )（邻接表+堆实现）
- 空间复杂度：
O(V + E)
-
Kruskal算法
- 时间复杂度：( O(E \log E + E \log V) )，主要来源于边排序和并查集操作。
- 空间复杂度：
O(E + V)
四、实验运行结果图
运行代码后，终端输出示例如下：
Prim 算法结果:
总权值: 16, 边: [(0, 1, 2), (1, 2, 3), (1, 4, 5), (0, 3, 6)]
Kruskal 算法结果:
总权值: 16, 边: [(0, 1, 2), (1, 2, 3), (1, 4, 5), (0, 3, 6)]
五、实验提交方式
- 文件夹结构：
学号+姓名/ ├── 实验报告.docx └── mst.py - 上传至指定云盘路径：
上电云盘/课程目录/20241216文件夹/ - 提交时间：课前15分钟，逾期无效。
如需修改或补充，请告诉我！