使用c++编写prim算法以无向网表示n个城市之间的通信网络计划,其中顶点表示城市,边上的权表示工程造价。请设计程序求出该通信网络总工程造价最低的建设方案。
时间: 2023-12-10 21:37:46 浏览: 94
下面是使用C++编写的Prim算法代码,实现求解无向网表示n个城市之间的通信网络计划,并输出最小生成树的总工程造价:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
const int INF = 0x7fffffff;
int n, m;
int g[MAXN][MAXN]; // 存储城市之间的边权
int d[MAXN]; // 存储城市到最小生成树的距离
bool vis[MAXN]; // 标记城市是否已加入最小生成树
int prim()
{
memset(d, INF, sizeof(d));
memset(vis, false, sizeof(vis));
d[1] = 0;
int ans = 0;
for (int i = 1; i <= n; i++)
{
int u = 0;
for (int j = 1; j <= n; j++) // 找到离最小生成树最近的城市
if (!vis[j] && (u == 0 || d[j] < d[u]))
u = j;
vis[u] = true;
ans += d[u];
for (int v = 1; v <= n; v++) // 更新与新加入城市相邻的城市到最小生成树的距离
if (!vis[v] && d[v] > g[u][v])
d[v] = g[u][v];
}
return ans;
}
int main()
{
cin >> n >> m;
memset(g, INF, sizeof(g));
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
g[u][v] = g[v][u] = w;
}
int ans = prim();
cout << ans << endl;
return 0;
}
```
上述代码中,首先定义了常量`MAXN`表示最大城市数,常量`INF`表示无穷大。然后定义了变量`n`表示城市数,变量`m`表示道路数。接着定义了二维数组`g`表示城市之间的边权,一维数组`d`表示城市到最小生成树的距离,以及一维数组`vis`表示城市是否已加入最小生成树。
主函数中首先输入城市数和道路数,并初始化二维数组`g`。然后调用Prim算法计算最小生成树的总工程造价,并输出结果。
在Prim算法中,首先将所有城市到最小生成树的距离全部初始化为无穷大,将第1个城市加入最小生成树,并将其到最小生成树的距离设为0。然后依次加入其它城市,每次选择离最小生成树最近的城市,并将其加入最小生成树。在加入新城市时,更新与其相邻的城市到最小生成树的距离。当所有城市都加入最小生成树时,计算总工程造价并返回结果。
以上就是使用C++编写Prim算法求解无向网表示n个城市之间的通信网络计划的方法。
阅读全文