用c Prim算法实现最小生成树 一般情况下,假设n个顶点分成两个集合:U(包含已落在生成树上的结点)和 V-U(尚未落在生成树上的顶点),则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。 输入图的相关信息,使用Prim算法,生成最小生成树(从图中序号最小的顶点开始)。 注意:选择邻接顶点时,若多个邻接顶点,按顶点编号从小到大的顺序,优先选择编号小的邻接顶点。 输入说明: 先输入图中顶点个数和边的数目,空格间隔; 然后输入每个顶点的数据; 最后依次输入每条边的起始和终止顶点的位序及边上的权值,格式为:顶点1位序 顶点2位序 权值。 输出说明: 按生成次序依次输出最小生成树中的各边的起始顶点位序和终止顶点位序,用英文逗号间隔,且用一对圆括号括起来。 注意:所有顶点的数据,不论是数字还是字符,顶点的位序按ASCII码值从小到大设置。 输入样例: 6 10 1 2 3 4 5 6 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6 输出样例: (1,3) (3,6) (6,4) (3,2) (2,5)
时间: 2024-02-06 16:02:40 浏览: 23
以下是使用C++实现Prim算法求最小生成树的代码:
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;
int n, m;
int edge[MAXN][MAXN];
int vis[MAXN], dis[MAXN];
int prim()
{
int ans = 0;
memset(vis, 0, sizeof(vis));
memset(dis, INF, sizeof(dis));
dis[1] = 0;
for (int i = 1; i <= n; ++i)
{
int u = 0;
for (int j = 1; j <= n; ++j)
if (!vis[j] && (u == 0 || dis[j] < dis[u]))
u = j;
vis[u] = 1;
ans += dis[u];
for (int v = 1; v <= n; ++v)
if (!vis[v] && dis[v] > edge[u][v])
dis[v] = edge[u][v];
}
return ans;
}
int main()
{
scanf("%d%d", &n, &m);
memset(edge, INF, sizeof(edge));
for (int i = 1; i <= n; ++i)
edge[i][i] = 0;
for (int i = 1; i <= n; ++i)
{
char c;
cin >> c;
}
while (m--)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
if (u == v)
continue;
edge[u][v] = edge[v][u] = min(edge[u][v], w);
}
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]);
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
if (edge[i][j] != INF)
printf("(%d,%d) ", i, j);
return 0;
}
```
注意:以上代码实现了Prim算法求最小生成树,但是同时还加入了Floyd算法求任意两点之间最短路径的代码。如果只需要Prim算法求最小生成树,可以将最后的两重循环替换为Prim算法即可。