做网站开发公司,西安培训网站建设,沈阳推广网站,天津画册设计公司一、最小生成树-prim算法
1.1 最小生成树概念
一幅图可以有很多不同的生成树#xff0c;比如下面这幅图#xff0c;红色的边就组成了两棵不同的生成树#xff1a;
对于加权图#xff0c;每条边都有权重#xff08;用最小生成树算法的现实场景中#xff0c;图的边权重… 一、最小生成树-prim算法
1.1 最小生成树概念
一幅图可以有很多不同的生成树比如下面这幅图红色的边就组成了两棵不同的生成树
对于加权图每条边都有权重用最小生成树算法的现实场景中图的边权重一般代表成本、距离这样的标量所以每棵生成树都有一个权重和。比如上图右侧生成树的权重和显然比左侧生成树的权重和要小。
那么最小生成树很好理解了所有可能的生成树包含所有顶点中权重和最小的那棵生成树就叫「最小生成树」。
1.2 稠密图-朴素prim
和djikstra很像
const int INF 0x3f3f3f3f; // 定义一个非常大的数用作无穷远的初始化值
int n; // n表示图中的顶点数
int g[N][N]; // 邻接矩阵用于存储图中所有边的权重
int dist[N]; // 用于存储其他顶点到当前最小生成树的最小距离
bool st[N]; // 用于标记每个顶点是否已经被加入到最小生成树中// Prim算法的实现返回最小生成树的总权重
int prim() {memset(dist, 0x3f, sizeof dist); // 初始化所有顶点到MST的距离为无穷远int res 0; // 存储最小生成树的总权重for (int i 0; i n; i) { // 主循环每次添加一个顶点到MSTint t -1; // 用于找到当前未加入MST且dist最小的顶点for (int j 1; j n; j) // 遍历所有顶点找到tif (!st[j] (t -1 || dist[t] dist[j]))t j;//t就是当前加入最小生成树的顶点if (i dist[t] INF) return INF; // 如果图不连通则返回INFif (i) res dist[t]; // 非首次迭代时累加到MST的距离st[t] true; // 将顶点t加入到MST中//再从T出发更新所有未加入顶点到T的距离用于下一轮新的T的更新for (int j 1; j n; j) // 更新其他所有顶点到MST的最小距离if (!st[j]) dist[j] min(dist[j], g[t][j]);}return res; // 返回最小生成树的总权重
}例题 #includecstring
#includeiostream
#includealgorithmusing namespace std;const int N 510,M 100010,INF 0x3f3f3f3f;int n,m;
int g[N][N];
int dist[N];
bool used[N];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((!used[j]) (t -1 || dist[t] dist[j]))t j;}used[t] true;//第一步的dist[t]为INFif(i dist[t] INF) return INF;if(i)res dist[t];for(int j 1;j n;j){if(!used[j])dist[j] min(dist[j],g[t][j]);}}return res;
}int main(){scanf(%d%d,n,m);//重要memset(g,0x3f,sizeof(g));for(int i 0;i m; i){int u,v,w;scanf(%d%d%d,u,v,w);g[u][v] g[v][u] min(g[u][v],w);}int r prim();if(r INF)puts(impossible);else printf(%d,r);return 0;
}
1.3 堆优化的prim-不常用且复杂一般用kruskal替代
省略
二、最小生成树-kruskal算法
1.并查集复习
1.1 并查集Union-Find算法
是一个专门针对「动态连通性」的算法我之前写过两次因为这个算法的考察频率高而且它也是最小生成树算法的前置知识
动态连通性
简单说动态连通性其实可以抽象成给一幅图连线。比如下面这幅图总共有 10 个节点他们互不相连分别用 0~9 标记 这里所说的「连通」是一种等价关系也就是说具有如下三个性质
1、自反性节点 p 和 p 是连通的。
2、对称性如果节点 p 和 q 连通那么 q 和 p 也连通。
3、传递性如果节点 p 和 q 连通q 和 r 连通那么 p 和 r 也连通。 现在我们的 Union-Find 算法主要需要实现这三个 API
class UF {
public:/* 将 p 和 q 连接 */void union(int p, int q);/* 判断 p 和 q 是否连通 */bool connected(int p, int q);/* 返回图中有多少个连通分量 */int count();
};
函数功能说明
比如说之前那幅图09 任意两个不同的点都不连通调用 connected 都会返回 false连通分量为 10 个。
如果现在调用 union(0, 1)那么 0 和 1 被连通连通分量降为 9 个。
再调用 union(1, 2)这时 0,1,2 都被连通调用 connected(0, 2) 也会返回 true连通分量变为 8 个。 初始化
怎么用森林来表示连通性呢我们设定树的每个节点有一个指针指向其父节点如果是根节点的话这个指针指向自己。比如说刚才那幅 10 个节点的图一开始的时候没有相互连通就是这样 代码如下
class UF {// 记录连通分量private:int count;// 节点 x 的父节点是 parent[x]int* parent;public:/* 构造函数n 为图的节点总数 */UF(int n) {// 一开始互不连通this-count n;// 父节点指针初始指向自己parent new int[n];for (int i 0; i n; i)parent[i] i;}/* 其他函数 */
}; union实现
操作如下 代码如下
class UF {// 为了节约篇幅省略上文给出的代码部分...public:void union(int p, int q) {int rootP find(p);int rootQ find(q);if (rootP rootQ)return;// 将两棵树合并为一棵parent[rootP] rootQ;// parent[rootQ] rootP 也一样count--; // 两个分量合二为一}/* 返回某个节点 x 的根节点 */int find(int x) {// 根节点的 parent[x] xwhile (parent[x] ! x)x parent[x];return x;}/* 返回当前的连通分量个数 */int count() {return count;}
}; connected实现
代码如下
class UF {
private:// 省略上文给出的代码部分...public:bool connected(int p, int q) {int rootP find(p);int rootQ find(q);return rootP rootQ;}
}; 1.2 平衡性优化-union优化
分析union和connected的时间复杂度我们发现主要 API connected和 union 中的复杂度都是 find 函数造成的所以说它们的复杂度和 find 一样。
find 主要功能就是从某个节点向上遍历到树根其时间复杂度就是树的高度。我们可能习惯性地认为树的高度就是 logN但这并不一定。logN 的高度只存在于平衡二叉树对于一般的树可能出现极端不平衡的情况使得「树」几乎退化成「链表」树的高度最坏情况下可能变成 N。
图论解决的都是诸如社交网络这样数据规模巨大的问题对于 union 和 connected 的调用非常频繁每次调用需要线性时间完全不可忍受。
关键在于 union 过程我们一开始就是简单粗暴的把 p 所在的树接到 q 所在的树的根节点下面那么这里就可能出现「头重脚轻」的不平衡状况比如下面这种局面 长此以往树可能生长得很不平衡。我们其实是希望小一些的树接到大一些的树下面这样就能避免头重脚轻更平衡一些。解决方法是额外使用一个 size 数组记录每棵树包含的节点数我们不妨称为「重量」
class UF {
private:int count;int* parent;// 新增一个数组记录树的“重量”int* size;public:UF(int n) {this-count n;parent new int[n];// 最初每棵树只有一个节点// 重量应该初始化 1size new int[n];for (int i 0; i n; i) {parent[i] i;size[i] 1;}}/* 其他函数 */
};
比如说 size[3] 5 表示以节点 3 为根的那棵树总共有 5 个节点。这样我们可以修改一下 union 方法
class UF {
private:// 为了节约篇幅省略上文给出的代码部分...
public:void union(int p, int q) {int rootP find(p);int rootQ find(q);if (rootP rootQ)return;// 小树接到大树下面较平衡if (size[rootP] size[rootQ]) {parent[rootQ] rootP;size[rootP] size[rootQ];} else {parent[rootP] rootQ;size[rootQ] size[rootP];}count--;}
};这样通过比较树的重量就可以保证树的生长相对平衡树的高度大致在 logN 这个数量级极大提升执行效率。
此时find , union , connected 的时间复杂度都下降为 O(logN)即便数据规模上亿所需时间也非常少。
1.3 路径压缩-find优化
其实我们并不在乎每棵树的结构长什么样只在乎根节点。
因为无论树长啥样树上的每个节点的根节点都是相同的所以能不能进一步压缩每棵树的高度使树高始终保持为常数 这样每个节点的父节点就是整棵树的根节点find 就能以 O(1) 的时间找到某一节点的根节点相应的connected 和 union 复杂度都下降为 O(1)。
要做到这一点主要是修改 find 函数逻辑非常简单但你可能会看到两种不同的写法。
方法1
class UF {// 为了节约篇幅省略上文给出的代码部分...private:int find(int x) {while (parent[x] ! x) {// 这行代码进行路径压缩parent[x] parent[parent[x]];x parent[x];}return x;}
};
每次使得当前x指向父节点的父节点这样会将一些节点向上移然后缩短树的长度 压缩结束为 方法二
class UF {// 为了节约篇幅省略上文给出的代码部分...// 第二种路径压缩的 find 方法public:int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]);}return parent[x];}
}; 其迭代写法如下便于理解
int find(int x) {// 先找到根节点int root x;while (parent[root] ! root) {root parent[root];}// 然后把 x 到根节点之间的所有节点直接接到根节点下面int old_parent parent[x];while (x ! root) {parent[x] root;x old_parent;old_parent parent[old_parent];}return root;
}
最终效果 1.4 并查集框架-优化后
class UF {
private:// 连通分量个数int count;// 存储每个节点的父节点int *parent;public:// n 为图中节点的个数UF(int n) {this-count n;parent new int[n];for (int i 0; i n; i) {parent[i] i;}}// 将节点 p 和节点 q 连通void union_(int p, int q) {int rootP find(p);int rootQ find(q);if (rootP rootQ)return;parent[rootQ] rootP;// 两个连通分量合并成一个连通分量count--;}// 判断节点 p 和节点 q 是否连通bool connected(int p, int q) {int rootP find(p);int rootQ find(q);return rootP rootQ;}int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]);}return parent[x];}// 返回图中的连通分量个数int count_() {return count;}
};
2.kruskal
给你输入编号从 0 到 n - 1 的 n 个结点和一个无向边列表 edges每条边用节点二元组表示请你判断输入的这些边组成的结构是否是一棵树。
如果输入
n 5
edges [[0,1], [0,2], [0,3], [1,4]] 这些边构成的是一棵树算法应该返回 true 输入
n 5
edges [[0,1],[1,2],[2,3],[1,3],[1,4]] 形成的就不是树结构了因为包含环 我们思考为何会产生环仔细体会下面两种添边的差别 总结一下规律就是
对于添加的这条边如果该边的两个节点本来就在同一连通分量里那么添加这条边会产生环反之如果该边的两个节点不在同一连通分量里则添加这条边不会产生环。
那么只需要在union两节点之前先检测两节点是否已经connection如果已连接所有添加后会生成环则返回false。同时需要注意count1不然就是森林了。
代码如下
class UF {
public:vectorint parent;UF(int n) {for (int i 0; i n; i) {parent.push_back(i);}}int find(int x) {while (x ! parent[x]) {parent[x] parent[parent[x]];x parent[x];}return x;}void union_(int p, int q) {int root_p find(p);int root_q find(q);parent[root_p] root_q;}bool connected(int p, int q) {int root_p find(p);int root_q find(q);return root_p root_q;}int count() {int cnt 0;for (int i 0; i parent.size(); i) {if (parent[i] i) {cnt;}}return cnt;}
};bool validTree(int n, vectorvectorint edges) {UF uf(n);// 遍历所有边将组成边的两个节点进行连接for (auto edge : edges) {int u edge[0];int v edge[1];// 若两个节点已经在同一连通分量中会产生环if (uf.connected(u, v)) {return false;}// 这条边不会产生环可以是树的一部分uf.union_(u, v);}// 要保证最后只形成了一棵树即只有一个连通分量return uf.count() 1;
} 3.连接所有点的最小费用-kruskal算法 所谓最小生成树就是图中若干边的集合我们后文称这个集合为 mst最小生成树的英文缩写你要保证这些边
1、包含图中的所有节点。
2、形成的结构是树结构即不存在环。
3、权重和最小。
有之前题目的铺垫前两条其实可以很容易地利用 Union-Find 算法做到关键在于第 3 点如何保证得到的这棵生成树是权重和最小的。
这里就用到了贪心思路
将所有边按照权重从小到大排序从权重最小的边开始遍历如果这条边和 mst 中的其它边不会形成环则这条边是最小生成树的一部分将它加入 mst 集合否则这条边不是最小生成树的一部分不要把它加入 mst 集合。
以此题为例 此题虽然是使用kruskal算法但是并不是直接套用还要有一些值得注意的事项
1我们要将题目中的给出点转换为点组合并且将权重添加进去
在题中只给出一个点的坐标我们需要想方法转换为两个点的链接所以需要将每个点两个坐标组合转换为一个符号标记在链接数组把相连的两个符号放一起就行了很明显我们使用0-n-1来记录每一个点是最合适的不仅方便遍历也一目了然
因此有如下代码 vectorvectorint edges;for(int i 0;i points.size();i){//此处不能写为int j 0,这样会重复导致超时根据求子集的思想应该从ji1开始for(int j i1;j points.size();j){// if(i j)continue;//因为ji1开始所有不需要这句判断int w1 abs(points[i][0]-points[j][0]);int w2 abs(points[i][1]-points[j][1]);edges.push_back({i,j,w1w2});}} 2我们要对得到的数组进行排序而且是对权重维度排序这就需要我们利用lambda来自定义sort的排序方式了
有代码如下 sort(edges.begin(),edges.end(),[](const vectorint a,const vectorint b){return a[2] b[2];});
依照kruskal算法可以写出如下完整代码
class uf{private:int count;vectorint parent;public:uf(int n){this-count n;// parent new int[n];parent.resize(n);for(int i0;i n;i){parent[i] i;}}int find(int x){if(parent[x]!x)parent[x] find(parent[x]);return parent[x];}void Union(int p,int q){int rootp find(p);int rootq find(q);if(rootp rootq)return;parent[rootp] rootq;count--;}bool connection(int p,int q){int rootp find(p);int rootq find(q);return rootp rootq;}
};class Solution {
public:int minCostConnectPoints(vectorvectorint points) {vectorvectorint edges;for(int i 0;i points.size();i){//此处不能写为int j 0,这样会重复导致超时根据求子集的思想应该从ji1开始for(int j i1;j points.size();j){// if(i j)continue;//因为ji1开始所有不需要这句判断int w1 abs(points[i][0]-points[j][0]);int w2 abs(points[i][1]-points[j][1]);edges.push_back({i,j,w1w2});}}sort(edges.begin(),edges.end(),[](const vectorint a,const vectorint b){return a[2] b[2];});uf uf(points.size());int sum_w 0;for(auto s : edges){int q s[0],p s[1],w s[2];if(uf.connection(p,q))continue;sum_w w;uf.Union(p,q);}return sum_w;}
};
