最小生成树 kruskal算法&prim算法

(先更新到这,后面有时间再补,嘤嘤嘤)

今天给大家简单的讲一下最小生成树的问题吧!(ps:本人目前还比较菜,所以最小生成树最后的结果只能输出最小的权值,不能打印最小生成树的路径)

本Tianc在刚学的时候,经常把最小生成树问题和最锻炼吧问题弄混淆,最后事实证明这两个问题是存在着相似点的。

所以还是可以参照我上一篇的博客 https://www.cnblogs.com/laysfq/p/9808088.html(此处插个"广告")

最小生成树的实质问题还是求最短的路径(是吧?肯定是的!)

kruskal算法(用边进行更新)

我的kruskal算法中用到了并查集,这样的话比较好找父结点,它的具体过程是这样的:

先将他们的权值进行映射排序,然后从最小的权值里面的取出结点数,放到树里面作为根结点,然后用并查集进行连接,每连接一个点,

把这条边所对应的权值加进去,查询下一个结点。不断的更新,直到把所有的点全部放到树里面。

下面是代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = ;
int n,m;
int u[maxn], v[maxn], w[maxn], pre[maxn], r[maxn];
int fun(int i, int j) {
return w[i] < w[j];
}
int find(int x) {
return pre[x] == x ? x : pre[x] = find(pre[x]);
}
int kruskal() {
int ans = ;
for (int i = ; i < n; ++i) pre[i] = i;
for (int i = ; i < m; ++i) r[i] = i;
sort(r, r + m, fun);
for (int i = ; i < m; ++i) {
int temp = r[i];
int x = find(u[temp]);
int y = find(v[temp]);
if (x != y) {
pre[x] = y;
ans += w[temp];
}
}
return ans;
} int main() {
while (cin >> n>> m) {
for (int i = ; i < m; ++i) {
cin >> u[i] >> v[i] >> w[i];
}
cout << kruskal() << endl;
}
}

最小生成树 kruskal算法&prim算法

呃呃呃,上面是程序运行的结果,第一行的5和7表示的是结点数和边的数目,下面会输入7行,例如“1  2  5”,表示的是1和2之间的权值是5。

最后输出最小生成树中权值总和。

Prim算法(用点进行更新)

这个是用点进行更新的,先将权值最小的边找出来,然后把最小的边对应的两个结点放进图中,然后利用这两个点向外不断的扩展,依据就是找出和这两个点相连且权值最小的且不在图里面的点。直到最后将所有的点访问完,构成一棵最小生成树。

附上代码:

#include<iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = ;
bool vis[MAXN];
int lowc[MAXN];
int Prim(int cost[][MAXN], int n)//点是1-n
{
int ans = ;
memset(vis, false, sizeof(vis));
vis[] = true;
for (int i = ; i<=n; i++)lowc[i] = cost[][i];
for (int i = ; i<=n; i++)
{
int minc = INF;
int p = -;
for (int j = ; j<=n; j++)
if (!vis[j] && minc>lowc[j])
{
minc = lowc[j];
p = j;
}
if (minc == INF)return -;//原图不连通
ans += minc;
vis[p] = true;
for (int j = ; j<=n; j++)
if (!vis[j] && lowc[j]>cost[p][j])
lowc[j] = cost[p][j];
}
return ans;
} int main() {
int n, m;
int a, b, c;
int cost[MAXN][MAXN];
while (cin >> n >> m) {
for (int i = ; i <= n; ++i) {
for (int j = ; j <= n; ++j) {
if (i == j) cost[i][j] = ;
else cost[i][j] = INF;
}
}
for (int i = ; i < m; ++i) {
cin >> a >> b >> c;
cost[a][b] = cost[b][a] = c;
}
cout << Prim(cost, n)<<endl;
}
}
上一篇:《BI那点儿事》ETL中的关键技术


下一篇:一个吊丝android个人开发者的逆袭之路