【问题描述】 现要在多个城市之间建设城际铁路,由于铁路建设费用昂贵,因此需合理安排建设线路,即以最少的资金投入,实现每个城市都能有城际铁路通达。 【基本要求】 (1)设计包含多个城市的平面图,所含城市数不少于10个,其中图中顶点表示城市,边表示城市之间的线路,边的权值表示建设所需的费用。 (2)可手动输入或随机生成城市的平面图信息,且图采用邻接数组或邻接表存储结构。 (3)基于普里姆算法,给出一种城际铁路建设方案,即输出应该建设的线路以及需要建设的总里程数。 【测试数据】 自行设计或者随机生成 【实现提示】 (1)运用邻接数组或邻接表存储该顶点数不少于10的无向图。 (2)运用普里姆算法合理安排建设线路。 【选做内容】 基于克鲁斯卡尔算法,给出一种或多种城际铁路建设方案。
时间: 2024-02-12 21:03:50 浏览: 21
以下是一个基于邻接表存储结构的Python实现,使用Prim算法来实现最小生成树,即最小费用的城际铁路建设方案:
```python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[] for i in range(vertices)]
def add_edge(self, u, v, w):
self.graph[u].append((v, w))
self.graph[v].append((u, w))
def prim_mst(self):
key = [float('inf')] * self.V
parent = [None] * self.V
visited = [False] * self.V
key[0] = 0
parent[0] = -1
for i in range(self.V - 1):
min_key = float('inf')
min_index = 0
for v in range(self.V):
if not visited[v] and key[v] < min_key:
min_key = key[v]
min_index = v
visited[min_index] = True
for v, w in self.graph[min_index]:
if not visited[v] and w < key[v]:
key[v] = w
parent[v] = min_index
print("需要建设的线路:")
total_distance = 0
for i in range(1, self.V):
print(f"({parent[i]}, {i}, {key[i]})")
total_distance += key[i]
print(f"需要建设的总里程数为:{total_distance}")
g = Graph(10)
g.add_edge(0, 1, 4)
g.add_edge(0, 7, 8)
g.add_edge(1, 2, 8)
g.add_edge(1, 7, 11)
g.add_edge(2, 3, 7)
g.add_edge(2, 8, 2)
g.add_edge(2, 5, 4)
g.add_edge(3, 4, 9)
g.add_edge(3, 5, 14)
g.add_edge(4, 5, 10)
g.add_edge(5, 6, 2)
g.add_edge(6, 7, 1)
g.add_edge(6, 8, 6)
g.add_edge(7, 8, 7)
g.add_edge(8, 9, 8)
g.prim_mst()
```
这个实现中,我们首先定义了一个`Graph`类,包含了顶点数量、邻接表等属性,以及添加边和使用Prim算法计算最小生成树的方法。在Prim算法中,我们使用了`key`列表来存储到每个顶点的最小权值,`parent`列表来存储每个顶点的父节点,`visited`列表来记录每个顶点是否已经被访问过。在Prim算法的主循环中,我们首先找到未访问的顶点中`key`值最小的顶点,将其标记为已访问,并更新其邻接表中的顶点的`key`值和`parent`值。最后,我们输出需要建设的线路和总里程数。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)