最小生成树

基本概念

- 解决图中，查找最小连通路径的问题

• 具体实现

  • Prim算法

    • 朴素版

      • 时间复杂度 $O(n^2)$
      • 对稠密图 常用

      • 代码实现

        • 每次找距离集合最近的点，如果这个点到集合的距离不是无穷，就用这个点来更新其他所有在集合之外的点到集合的距离 dist[i] = min(dist[i], g[t][i]) （此时注意与 ((65141379-5191-4ab2-a316-8d3cb6afc2fe)) 的区别，这里的是直接用 g[t][i] 更新而不是 dist[t] + g[t][i]

        • int prim()
          {
          	memset(d, 0x3f, sizeof d);
            	for(int i = 0; i < n; i ++) // 循环n次
              {
                	int t = -1; 
                  for(int j = 1; j <= n; j ++)  // 找距离最小
                  {
                     if(!s[j] && (t == -1 || d[j] < d[t]))
                        t = j;
          		}
                
                	if(i && d[t] == INF)  return INF;  //除第一个其他都不能为无穷
                	if(i) ans += d[t];  // 除第一个加权
                
                	for(int j = 1; j <= n; j ++)
                  {
                    	d[j] = min(d[j], g[t][j]);
                  }
                
                	s[t] = true;  // 加入集合
              }
          }

    • 堆优化版

      • 时间复杂度$O(mlogm)$
      • 对稀疏图 少用

  • Kruskal算法

    • 克鲁斯卡尔算法
    • 对稀疏图
    • 时间复杂度$O(mlogm)$

    • 具体

      • 实现为 将边从小到大排序
      • 排序过后按序查找每条边，回插到图中，如果边的两点没有连通，那就记入最小生成树，否则就pass掉（相当于抽出所有边排序后再回插最小的）
      • 每次插入就计数，如果插入所有边后，计数结果小于 n ，认为有的点还没有连上，但是边已经没有了，则这个图不连通，无最小生成树
      • 查是否连通
        • 使用 并查集 查根节点是否相同，相同则连通

    • 代码

      • struct Edge
        {
          	int a, b, w;
          
          	bool operator < (const Edge & W)const  // 结构体使用sort需要重载运算符
            {
              	return w < W.w;
            }
        }edge[N];
         
         
        int find(int x)
        {
          	if(p[x] != x)  p[x] = find(p[x]);  // 并查集
          	return p[x];
        }
         
         
         
        int main()
        {
        	for(int i = 0; i < m; i ++)
            {
                cin >> edge[i].a >> edge[i].b >> edge[i].w;
            }
          
          	sort(edge, edge + m); // 都是以边为主
          
          	for(int i = 0; i < m; i ++)
              p[i] = i;  // 并查集初始化
          
          	int ans = 0, cnt = 0;
          	for(int i = 0; i < m; i ++)
            {
              	int a = edge[i].a, b = edge[i].b;
                a = find(a);  b = find(b);
         
                if(a != b)
                {   
                    p[a] = b;  // 更新连通情况
                    ans += edge[i].w;
                    cnt ++;  // 计数
                }
        	}
          
          	if(cnt < n - 1)  cout << "impossible" << endl;
          	else  cout << ans << endl;
          
          	return 0;
        }