158 lines
4.1 KiB
Markdown
158 lines
4.1 KiB
Markdown
以下是实验报告框架和 Python 实现的模板，供参考：
|
||
|
||
---
|
||
|
||
### 实验报告：最小生成树
|
||
|
||
#### 学号：XXXXXX
|
||
#### 姓名：XXXXXX
|
||
|
||
---
|
||
|
||
#### **一、最小生成树基本思想**
|
||
|
||
最小生成树（Minimum Spanning Tree, MST）是一个无向连通图的一个子图，满足以下条件：
|
||
1. 是连通图；
|
||
2. 包含图中所有顶点，但只包含 \( n-1 \) 条边（其中 \( n \) 为顶点数）；
|
||
3. 所有边的权值之和最小。
|
||
|
||
常用的算法包括：
|
||
- **Prim算法**：逐步扩展生成树，通过选择权值最小的边加入生成树。
|
||
- **Kruskal算法**：先按权值对边排序，再通过判断是否形成环来选择边加入生成树。
|
||
|
||
---
|
||
|
||
#### **二、源码**
|
||
以下代码实现了 Prim 和 Kruskal 两种算法：
|
||
|
||
```python
|
||
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}")
|
||
```
|
||
|
||
---
|
||
|
||
#### **三、算法分析**
|
||
|
||
1. **Prim算法**
|
||
- **时间复杂度**：\( O(V^2) \)（邻接矩阵实现）或 \( O(E \log V) \)（邻接表+堆实现）
|
||
- **空间复杂度**：\( O(V + E) \)
|
||
|
||
2. **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分钟，逾期无效。
|
||
|
||
---
|
||
|
||
如需修改或补充，请告诉我！ |