普同网站跟营销型网站的区别,网站点赞功能,wordpress多语言设置,百度提交收录在连通网的所有生成树中#xff0c;所有边的代价和最小的生成树#xff0c;称为最小生成树。解决最小生成树问题一般有两种算法#xff1a;Kruskal算法和Prim算法。
Kruskal算法
原理#xff1a;基本思想是从小到大加入边#xff0c;是个贪心算法。我们将图中的每个边按… 在连通网的所有生成树中所有边的代价和最小的生成树称为最小生成树。解决最小生成树问题一般有两种算法Kruskal算法和Prim算法。
Kruskal算法
原理基本思想是从小到大加入边是个贪心算法。我们将图中的每个边按照权重大小进行排序每次从边集中取出权重最小且两个顶点都不在同一个集合的边加入生成树中。注意如果这两个顶点都在同一集合内说明已经通过其他边相连因此如果将这个边添加到生成树中那么就会形成环。这样反复做直到选出n-1条边。时间复杂度为O(m*logm)
算法过程此算法可以称为“加边法”初始最小生成树边数为0每迭代一次就选择一条满足条件的最小代价边加入到最小生成树的边集合里。 具体过程如下所示 步骤1先对图中所有的边按照权值进行排序 步骤2如果当前这条边的两个顶点不在一个集合里面那么就用并查集的Union函数把他们合并在一个集合里面(也就是把他们放在最小生成树里面)如果在一个并查集里面我们就舍弃这条边不需要这条边。 步骤3一直执行步骤2知道当边数等于n-1n为节点个数那就说明这n个顶点就连合并在一个集合里面了如果边数不等于顶点数目减去1那么说明这些边就不连通即无法构成最小生成树。
代码框架
int n, m; // n是点数m是边数
int p[n 1]; // 并查集的父节点数组
struct Edge{ // 存储边 int a, b, w; bool operator (const Edge W)const { return w W.w; }
}edges[m];
int find(int x){ // 并查集核心操作 return p[x] x ? x : p[x] find(p[x]);
}
void init(){ // 初始化并查集 for(int i 1; i n; i){p[i] i;}
}
int kruskal() {sort(edges, edges m); init();int res 0, cnt 0; for (int i 0; i m; i) { // 从m条边选择n-1条边int a edges[i].a, b edges[i].b, w edges[i].w; a find(a), b find(b); if (a ! b) { // 如果两个连通块不连通则将这两个连通块合并p[a] b; res w; cnt; } }if (cnt n - 1) return INF; return res;
}
Prim算法
原理基本思想是从一个结点开始不断加点。因此该算法可以称为“加点法”每次迭代选择代价最小的边对应的点加入到最小生成树中。算法从某一个顶点s开始逐渐长大覆盖整个连通网的所有顶点。时间复杂度为O(n * n m)。
算法过程 用两个集合A{}B{}分别表示找到的点集和未找到的点集 我们以A中的点为起点a在B中找一个点为终点b这两个点构成的边ab的权值是其余边中最小的 重复上述步骤#2直至B中的点集为空A中的点集为满
代码框架
int n; // 节点个数
vectorvectorint g(n, vectorint(n)); // 邻接矩阵存储所有边
vectorint dis(n); // 存储其他节点到当前最小生成树的距离
vectorbool v(n); // 存储每个节点是否加入到最小生成树中
// 如果图不连通则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){const int inf 0x3f3f3f3f;memset(dis, 0x3f, sizeof dis);int res 0;for(int i 0; i n; i){int p -1;for(int j 0; j n; j){if(!v[j] (p -1 || dis[j] dis[p])){p j;}}if(i dis[p] inf){ // dis[p] inf说明找到的节点与最小生成树不连通但是当i 0说明是第一个节点不考虑连通return inf;}if(i){res dis[p];}v[p] true;for(int j 0; j n; j){dis[j] min(dis[j], g[p][j]); // 与Dijkstra算法的区别}}return res;
}
题单
1584. 连接所有点的最小费用 - 力扣LeetCode
