图的最小生成树
1.树和图的根本区别: 树不会包含环, 图可以包含环
2.图的 [生成树] 是: 包含图中所有订单的无环连通子图; [最小生成树] (Minimum Spanning Trees), 我把它称之为最小跨越树, 指所有的生成树中权重和最小的那颗生成树, 以下简称mst; Span: 跨越：extend from side to side of xx, eg: the stream was spenned by a narrow bridge
3.krusal 算法是一种求解最小生成树的问题的方法, 这种方法首先要基于并查集的方法, 回顾 union-find 算法如下
class UF {
private:
vector<int> parent; // 保存所有节点的父节点
int count; // 保存连通分量的个数
public:
UF(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
count = n;
}
bool ifConnected(int p, int q) {
int rootP = findRoot(p);
int rootQ = findRoot(q);
return (rootP == rootQ) ? true : false;
}
int findRoot(int x) {
if (x != parent[x]) {
parent[x] = findRoot(parent[x]);
}
return parent[x];
}
void union(int p, int q) {
int rootP = findRoot(p);
int rootQ = findRoot(q);
if (rootP == rootQ)
return;
parent[rootP] = rootQ;
--count;
return;
}
};
4.并查集为我们提供了一种合并等价类的实现方法, 有了 uf 的基础结构, 我们考虑如何生成一颗权重和最小的树
5.Kruskal 算法: 采用贪心的思路逐步进行最小生成树的生成, 其实相当于我们对所有节点集合做某一种并查集, 但这种并查集有特殊的目标是: 必须保证最后边路径和加最小, 所以在对每组边做合并的时候, 都是挑选权重最小边的做节点的并查集, 这样能保证最后的边路径加和最小; 其中在做并查集的时候需要判定没有环的存在, 也就是当前的union的两个节点必须保证没有形成连通分量的, 这样可以保证并查集的结果是生成树, 也就是连通分量的个数最终=1
Kruskal 算法的思路如下:
1.首先将所有边按照权重进行排序, 然后逐次遍历所有的边, 如果这条边和 mst 中的其他边不会形成环, 则这条边是最小生成树的一部分, 直接进行 union; 否则这条边不是最小生成树的一部分, 依次累加 union 的权重可以得到最小生成树的最小权重和.
2.当一棵树没有办法生成最小生成树的时候, 例如整个城市由多个子图构成无法生成生成树, 那么需要从连通分量的个数去判断是否生成了最小生成树, 如果能生成最小生成树, 那么连通分量的个数最终为 1
// Kruskal algorithm
class Solution {
private:
vector<int> parent;
int count;
public:
static bool cmp(vector<int>& a, vector<int>& b) {
return a[2] < b[2];
}
int findRoot(int x) {
if (x != parent[x]) {
parent[x] = findRoot(parent[x]);
}
return parent[x];
}
bool ifConnected(int p, int q) {
return (findRoot(p) == findRoot(q)) ? true : false;
}
void unionNode(int p, int q) {
int rootP = findRoot(p);
int rootQ = findRoot(q);
if (rootP == rootQ)
return;
parent[rootP] = rootQ;
--count;
return;
}
// connections里面存储从0开始的节点pair以及weight, 例如[0,2,5]
int minimumCost(int n, vector<vector<int>>& connections) {
int minCost = 0;
parent.resize(n);
count = n;
for (int i = 0; i <= n; ++i) {
parent[i] = i;
}
sort(connections.begin(), connections.end(), cmp);
for (vector<int>& connection : connections) {
int p = connection[0];
int q = connection[1];
int weight = connection[2];
if (ifConnected(p, q)) {
continue;
}
unionNode(p, q);
minCost += weight;
}
return count == 1 ? minCost : -1;
}
};
1135.最低成本联通所有城市
想象一下你是个城市基建规划者，地图上有 n 座城市，它们按以 1 到 n 的次序编号。给你整数 n 和一个数组 conections，其中 connections[i] = [xi, yi, costi] 表示将城市 xi 和城市 yi 连接所要的costi（连接是双向的）。 返回连接所有城市的最低成本，每对城市之间至少有一条路径。如果无法连接所有 n 个城市，返回 -1 该 最小成本 应该是所用全部连接成本的总和。
示例 1：输入：n = 3, conections = [[1,2,5],[1,3,6],[2,3,1]] 输出：6 解释：选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。
示例 2：输入：n = 4, conections = [[1,2,3],[3,4,4]] 输出：-1 解释：即使连通所有的边，也无法连接所有城市。
分析:
1.所有节点能被连通的条件是 uf.count == 1, 这题下标从 0 开始的, 相应的并查集父节点保存 size 为 n+1, 默认连通分量的个数为 n+1, 所以最终判定生成最小生成树的条件为 uf.count == 2
class Solution {
private:
vector<int> parent;
int count;
public:
static bool cmp(vector<int>& a, vector<int>& b) {
return a[2] < b[2];
}
int findRoot(int x) {
if (x != parent[x]) {
parent[x] = findRoot(parent[x]);
}
return parent[x];
}
bool ifConnected(int p, int q) {
return (findRoot(p) == findRoot(q)) ? true : false;
}
void unionNode(int p, int q) {
int rootP = findRoot(p);
int rootQ = findRoot(q);
if (rootP == rootQ)
return;
parent[rootP] = rootQ;
--count;
return;
}
int minimumCost(int n, vector<vector<int>>& connections) {
int minCost = 0;
parent.resize(n+1);
count = n+1;
for (int i = 0; i <= n; ++i) {
parent[i] = i;
}
sort(connections.begin(), connections.end(), cmp);
for (vector<int>& connection : connections) {
int p = connection[0];
int q = connection[1];
int weight = connection[2];
if (ifConnected(p, q)) {
continue;
}
unionNode(p, q);
minCost += weight;
}
return count == 2 ? minCost : -1;
}
};
1584.连接所有点的最小费用
给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。示例 1：输入：points = [
[0,0],[2,2],[3,10],[5,2],[7,0]
] 输出：20 解释：我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。注意到任意两个点之间只有唯一一条路径互相到达。示例 2：输入：points = [
[3,12],[-2,5],[-4,1]
] 输出：18示例 3：输入：points = [
[0,0],[1,1],[1,0],[-1,1]
] 输出：4示例 4：输入：points = [
[-1000000,-1000000],[1000000,1000000]
] 输出：4000000示例 5：输入：points = [
[0,0]
] 输出：0
分析:
1.曼哈顿距离计算可以得到边的权重, 然后算坐标点之间的最小生成树
2.因为单个点是用二维坐标去描述的, 因此这里描述一条边需要一个五元组, 但这样的话写uf算法会比较繁琐; 这里可以先构建辅助 connections 数组, 对原始的二维坐标点转化成 index, 也就是将二维坐标点的index作为图节点的index再去做并查集, 同时计算出来曼哈顿距离, 也就是保存成 [point_idx_i, point_idx_j, manhattan_dist]
3.这道题采用 Kruskal 可 ac 但效率低5%, 后续想想如何优化
class Solution {
private:
vector<vector<int>> connections;
vector<int> parent;
int count;
int minCost = 0;
public:
static bool cmp(vector<int>& a, vector<int>& b) {
return a[2] < b[2];
}
int findRoot(int x) {
if (x != parent[x]) {
parent[x] = findRoot(parent[x]);
}
return parent[x];
}
bool ifConnected(int p, int q) {
return (findRoot(p) == findRoot(q)) ? true : false;
}
void unionData(int p, int q) {
int rootP = findRoot(p);
int rootQ = findRoot(q);
if (rootP == rootQ)
return;
parent[rootP] = rootQ;
return;
}
int minCostConnectPoints(vector<vector<int>>& points) {
for (int i = 0; i < points.size(); ++i) {
for (int j = i + 1; j < points.size(); ++j) {
int i_x = points[i][0];
int i_y = points[i][1];
int j_x = points[j][0];
int j_y = points[j][1];
int weight = abs(i_x-j_x) + abs(i_y-j_y);
connections.push_back({i, j, weight});
}
}
parent.resize(points.size());
for (int i = 0; i < parent.size(); ++i) {
parent[i] = i;
}
sort(connections.begin(), connections.end(), cmp);
for (vector<int> connection : connections) {
int p = connection[0];
int q = connection[1];
int w = connection[2];
if (ifConnected(p, q)) {
continue;
}
unionData(p, q);
minCost += w;
}
return minCost;
}
};
261.以图判树
给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。
如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。示例 1：输入: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] 输出: true
示例 2: 输入: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] 输出: false
分析:
1.判定树结构的条件: 如果图里面有环, 那么一定不能产生一棵树, 但只判断图里面是否有环还不够充分; 要用到所有的节点生成树结构, 所以要生成一颗生成树, 仍然采用并查集的方法进行逐个union, 最终得到的连通分量的个数只能是1; 因此采用生成并查集的方式去判定
class Solution {
private:
vector<int> parent;
int count;
public:
int findRoot(int x) {
if (x != parent[x]) {
parent[x] = findRoot(parent[x]);
}
return parent[x];
}
bool ifConnected(int p, int q) {
return (findRoot(p) == findRoot(q)) ? true : false;
}
void unionData(int p, int q) {
int rootP = findRoot(p);
int rootQ = findRoot(q);
if (rootP == rootQ)
return;
parent[rootP] = rootQ;
--count;
return;
}
bool validTree(int n, vector<vector<int>>& edges) {
parent.resize(n);
count = n;
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
for (vector<int> edge : edges) {
int p = edge[0];
int q = edge[1];
if (ifConnected(p, q)) {
return false;
}
unionData(p, q);
}
return (count == 1) ? true : false;
}
};
转载请注明来源, from goldandrabbit.github.io
