【算法基础】图解 最小生成树

---

• 最小生成树:稠密图用Prim 稀疏图用 Kruskral

普利姆算法(Prim) O(n²) 【稠密图】

思路:
①初始化
②迭代n次：
每次迭代一个点，更新该点到它可以走到的所有点的最短距离
更新完 就把这个点加入到集合里面去
然后寻找下一个距离迭代过的点中距离最近的点

建图


下图为最小生成树

GIF↓

题目链接

/*
S:当前已经在联通块中的所有点的集合
1. dist[i] = inf
2. for n 次
    t<-S外离S最近的点
    利用t更新S外点到S的距离
    st[t] = true
n次迭代之后所有点都已加入到S中
联系：Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离
*/

#include 
#include 
#include 
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N];//存储图
int dist[N];//存储各个节点到生成树的距离
bool st[N];//节点是否被加入到生成树中
int n, m;//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(!st[j] && (t == -1 || dist[t] > dist[j])) {
        t = j;//寻找离集合S最近的点 
      }
    }
      if(i && dist[t] == INF) {
        //如果不是第一个点 并且该点没有值则该点一定不联通
        return INF;
      }
      if(i) {
        res += dist[t];
      }
      st[t] = true;//加到集合
      for (int j = 1; j <= n; j ++ ) {
        dist[j] = min(dist[j], g[t][j]);
      }
  }
  return res;
}

int main () {
  cin >> n >> m;
  memset(g, 0x3f, sizeof g);
  while (m --) {
    int a, b, w;
    cin >> a >> b >> w;
    g[a][b] = g[b][a] = min(g[a][b], w);//建立无向图[有向图的基础上+反边]
  }
  int t = prim();
  if (t == INF) {
    puts("impossible");
  } else {
    cout << t << endl;
  }
  return 0;
}

克鲁斯卡尔(Kruskal) O(mlogm)【稀疏图】

思路 ： 并查集
①排序所有点边
②需要定义res 存储权重 cnt存储集合中边的数量
循环n次
如果这条边不在集合内 ，就加到集合中去
就这么easy。还有一个语法问题。如何排序所有点边？？

//写法1
struct Edge {
	int a, b, w;
}edges[M];
bool cmp(struct Edge &a,struct Edge &b) {
	return a.w<b.w;
}
sort(edges, edges + m,cmp);
//写法2
struct Edge {
  int a, b, w;//利用到了运算符重载
  //类型转换函数通常是const 【形式：operator type() const 】
  bool operator< (const Edge &W)const {//从小到大排序
    return w < W.w;	
  }
}edges[N]; 
/*
重载小于号(<)，因为在给边排序的时候是按照边的权重进行排序的，也就
是说在struct Edge里面写了这个后，假如a和b都是struct Edge类型
的变量的话，a

语法问题可以参考这篇文章

图解

题目链接

Ｃ++代码

#include 
#include 
#include 
using namespace std;
const int N = 200010, M = 100010;
int n,m;
int p[M];

struct Edge {
  int a, b, w;
  bool operator< (const Edge &W)const {//从小到大排序
    return w < W.w;
  }
}edges[N]; 

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void kruskal() {
  int res = 0, cnt = 0;//res:最小生成树的树边权重之和,cnt:全部加入到树的集合中边的数量(可能有多个集合)
  for(int i = 0; i < m; i ++) {
    int a = edges[i].a,b = edges[i].b, w = edges[i].w;
    if(find(a) != find(b)) {//如果不在同一个连通块
      p[find(a)] = p[find(b)];//把a加到b集合里面去
      cnt ++;//记录该集合边数
      res += w;
    }
  }
  if(cnt == n - 1) {//树中有n个节点便有n-1条边的生成树
    cout << res << endl;//可以生成最小生成树
  } else {
    puts("impossible");
  }
}

int main () {
  cin >> n >> m;//n 为结点数  
  for(int i = 0; i < n; i ++) {
    p[i] = i;//并查集的初始化 
  }
  for(int i=0;i<m;i++) {
    int a,b,w;
    cin >> a >> b >> w;
    edges[i]={a,b,w};
  }
  sort(edges, edges + m);
  kruskal();
  return 0;
}

🌹感谢阅读🌹