大家好，欢迎来到IT知识分享网。
-
运行结果
-
方法一：Prim算法
#include <iostream>
using namespace std;
const int INF = 0x3fffffff;
const int N = 100;
int city[N][N]; //邻接矩阵
bool used[N]; //已经经过的城市
int point[N],edge[N]; //最邻近点，以及到最邻近点的边值
void Prim(int n,int u)
{
used[u] = true;
for(int i=1;i<=n;i++)
{
if(i==u)
point[i] = 0;
else
{
point[i] = u;
edge[i] = city[u][i];
used[i] = false;
}
}
int u0=u;
for(int i=1;i<=n;i++)
{
int temp = INF;
for(int j=1;j<=n;j++)
{
if(!used[j] && edge[j]<temp)
{
u0 = j;
temp = edge[j];
}
}
if(u0 == u)
break;
used[u0] = true;
for(int j=1;j<=n;j++)
{
if(!used[j] && city[u0][j]<edge[j])
{
edge[j] = city[u0][j];
point[j] = u0;
}
}
}
}
int main()
{
int n,m,u,v,w;
cout << "输入结点数n和边数m：";
cin >> n >> m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
city[i][j] = INF;
cout << "输入结点数u，v和边值w：" << endl;
for(int i=1;i<=m;i++)
{
cin >> u >> v >> w;
city[u][v] = w;
city[v][u] = w;
}
cout << "输入任一结点：";
cin >> u;
int sum = 0;
Prim(n,u);
for(int i=1;i<=n;i++)
sum += edge[i];
cout << "最小花费是：" << sum << endl;
return 0;
}
- 方法二：Kruskal算法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100;
struct Edge
{
int v;
int u;
int w;
}e[N];
int father[N];
bool cmp(Edge a,Edge b)
{
return a.w < b.w;
}
void Init(int n)
{
for(int i=1;i<=n;i++)
father[i] = i;
}
int FindFather(int i)
{
if(i == father[i])
return i;
else
{
int f = FindFather(father[i]);
father[i] = f;
return f;
}
}
int Kruskal(int n,int m)
{
int sum = 0;
for(int i=1;i<=m;i++)
{
int fv = FindFather(e[i].v);
int fu = FindFather(e[i].u);
if(fu != fv)
{
sum += e[i].w;
father[fv] = fu;
n--;
if(n == 1)
return sum;
}
}
return 0;
}
int main()
{
int n,m;
cout << "输入结点数n和边数m：";
cin >> n >> m;
cout << "输入结点数u，v和边值w：" << endl;
for(int i=1;i<=m;i++)
{
cin >> e[i].v >> e[i].u >> e[i].w;
}
sort(e+1,e+m+1,cmp);
Init(n);
cout << "最小花费是：" << Kruskal(n,m) << endl;
return 0;
}
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/12723.html
