滕州网站搜索引擎优化,自己做网站系统首选平台,做犯法任务的网站,网站建设和维护工作内容1、Kruskal算法
步骤与基本思路
#xff08;1#xff09;初始化所有点#xff0c;每个点单独在一个点集。把所有边按权重排序
#xff08;2#xff09;按边权重从小到大遍历每一条边#xff0c;如果这条边的两个顶点不在同一个点集#xff0c;就将它们加到同一点集1初始化所有点每个点单独在一个点集。把所有边按权重排序
2按边权重从小到大遍历每一条边如果这条边的两个顶点不在同一个点集就将它们加到同一点集也就是选中这条边以此类推
3如果最后加入同一个点集的点个数小于n个说明这个图不是连通图无法生成最小生成树
Kruskal板子
struct Edge
{int a, b, w;bool operator (const Edge W) const{return w W.w;}
}edges[M];int find(int x) // 判断x属于哪一个点集
{if (x ! p[x]) p[x] find(p[x]);return p[x];
}int kruskal()
{sort(edges, edges m); // 所有边按权重排序for (int i 1; i n; i ) p[i] i; // 所有点单独占一个点集int res 0, cnt 0;for (int i 0; i m; i ) // 从小到大遍历每条边{int a edges[i].a, b edges[i].b, w edges[i].w;a find(a), b find(b);if (a ! b) // 判断ab在不在同一个点集{p[a] b; // 合并到同一点集res w;cnt ;}}if (cnt n - 1) return INF; // 不是连通图return res;
}
2、Prim算法
步骤与基本思路
1初始化距离数组dist[N]将其所有值赋为0x3f
2从第一个点开始循环n次因为最小生成树有n个点每次循环中遍历所有点选择还没有加入最小生成树且与生成树集合距离最短的点加入生成树然后更新所有点到生成树集合的距离
3如果不是第一个点且距离生成树集合为无穷大时说明不能形成最小生成树
Prim板子
int prim() // 返回最小生成树的权重和
{memset(dist, 0x3f, sizeof dist);int res 0;for (int i 0; i n; i ){int t -1;for (int j 1; j n; j ) // 找到距离生成树集合距离最短的点if (!st[j] (t -1 || dist[t] dist[j]))t j;if (i dist[t] INF) return INF; // 距离最短的点距离时INFif (i) res dist[t];st[t] true;for (int j 1; j n; j ) dist[j] min(dist[j], g[t][j]); // 更新所有点到生成树集合的距离}return res;
}
