最小生成树
问题描述：一个有n户人家的村庄，有m条路连接着。村里现在要修路，每条路都有一个代价，现在请你帮忙计算下，最少需要花费多少的代价，就能让这n户人家连接起来。
示例
输入：3,3,[[1,3,3],[1,2,1],[2,3,1]]
返回值：2
说明：见下图，n户人家相连接不一定需要直达，所以只需要修建1与2之间，2与3之间的道路即可。
方法一
思路分析
本题题目即为最小生成树，因此求解最小生成树的算法有：普里姆算法—Prim算法、克鲁斯卡算法。因此方法一首先介绍Prim算法。其算法思想步骤如下：
- 设置初始集合$S$，初始为空，设总的节点集合$V$
- 首先图中任意节点1放入初始节点集合中$S={1}$，寻找与1有关联的边，寻找其权值最小的边，且连接的点2在集合$V-S$，如果寻找到则将其放入$S={1,2}$，并将该边的权值记录下来
- 接着寻找与$1，2$相关联的边，方法与上述相同
- 当$S=V$，最小生成树生成，程序结束
图解
输入：4,5,[[1,3,3],[1,2,1],[2,3,1],[2,4,2],[3,4,4]]
返回值：4
算法过程如图所示
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int n户人家的村庄
* @param m int m条路
* @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int
*/
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
// write code here
vector<int> visited(n,0);
visited[0] = 1;
int len = 0;
vector<int> adjset(n);
vector<vector <int> > map(n ,vector<int>(n,INT_MAX));
for(int i=0;i<m;i++)
{
map[cost[i][0]-1][cost[i][1]-1]=cost[i][2];
map[cost[i][1]-1][cost[i][0]-1]=cost[i][2];
}
for(int i=0;i<n;i++)
map[i][i]=0;
for (int i=0;i<n;i++)
adjset[i] = map[i][0];//计算只有一个节点与其他节点的距离值
for (int i=1;i<n;i++)
{
int nlen = INT_MAX;
int nid=0;
for (int j=0;j<n;j++)
{
if (!visited[j] && adjset[j]<nlen)
{
nlen = adjset[j];
nid = j;
}
}
len += nlen;
visited[nid] = 1;//标记已经访问过的点
for (int j=0;j<n;j++)
{
if (!visited[j] && map[j][nid]<adjset[j])
{
adjset[j] = map[j][nid];
}
}
}
return len;
}
}; 复杂度分析
- 时间复杂度：从点出发，每次寻找一个点，代码中存在内外两层嵌套循环，循环次数为$1+2+3+..+n=n*(n+1)/2$，其时间复杂度为$O(n^2)$
- 空间复杂度：借助于一个$n$大小的标记数组用于标记点是否访问过，借助于一个大小为$n$距离节点用于存储已经标记的点到其他点的距离，借助于一个$n^2$的二维数组存储图，因此总的空间复杂度为$O(n^2)$
方法二
思路分析
克鲁斯卡尔算法的基本思想为：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。
其中最难处理的是判断是否会产生回路，其方法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。
图解
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int n户人家的村庄
* @param m int m条路
* @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int
*/
int p[100010];
int find(int x)//查找结点与路径
{
if(x != p[x])
p[x] = find(p[x]);
return p[x];
}
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
// write code here
for(int i = 0; i <= n; i++)
p[i] = i;//对每一个顶点进行标记，标记不同
sort(cost.begin(),cost.begin() + m, [](vector<int>& l1, vector<int> & l2){
return l1[2] < l2[2];//按照权值从小到大排序
});
int sum = 0;//计算最短权值
for(int i = 0; i < m; i++)
{
if(find(cost[i][0]) != find(cost[i][1]))//不是同一个的话就进入循环
{
sum += cost[i][2];//将值计算进最终结果中
p[find(cost[i][0])] = find(cost[i][1]);//将加入的边的两个点标记一致
}
}
return sum;
}
}; 复杂度分析
- 时间复杂度：从边出发，首先需要对所有的边排序，接着每次寻找权值最小的边，因此总的时间复杂度为$O(m\log m)$
- 空间复杂度：借助于一个大小为$n$标记数组用于将每个节点标记为不同，空间复杂度为$O(n)$
京公网安备 11010502036488号