图论 - 最小生成树（Prime、Kruskal）

文章目录

• 前言
• Part 1：Prim算法求最小生成树
• • 1.题目描述
  • • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例
      • 输出样例
      • 2.算法
      • Part 2：Kruskal算法求最小生成树
      • • 1.题目描述
        • • • 输入格式
            • 输出格式
            • 数据范围
            • 输入样例
            • 输出样例
            • 2.���法

              前言

              本篇博客介绍两种求最小生成树的方法：即Prime算法和Kruskal算法。Prime算法用于稠密图，也可以与Dijkstra类似用堆优化（详见《图论 - 最短路（Dijkstra、Bellman-Ford、SPFA、Floyd）》），用于稀疏图，但是稀疏图的时候求最小生成树，Kruskal 算法更加实用，所以本篇博客将不介绍堆优化的Prime算法。即：稠密图用朴素Prime算法，稀疏图用Kruskal 算法即可。

              Part 1：Prim算法求最小生成树

              1.题目描述

              给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

              求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

              给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。

              由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

              输入格式

              第一行包含两个整数 n 和 m。

              接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

              输出格式

              共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

              数据范围

              1≤n≤500,

              1≤m≤105,

              图中涉及边的边权的绝对值均不超过 10000。

              输入样例

              4 51 2 11 3 21 4 32 3 23 4 4

              输出样例

              6

              2.算法

              • prim 算法采用的是一种贪心的策略
              • prim 算法做的事情是：给定一个无向图，在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中，叫做求最小生成树
              • 每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小
              • 与Dijkstra算法求最短路唯一的区别在于所求距离并非该点到源点的距离（详见《图论 - 最短路（Dijkstra、Bellman-Ford、SPFA、Floyd）》），而是该点到已选点集合的最短距离

                #include #include #include using namespace std;const int N = 510;int g[N][N];//存储图int dt[N];//存储各个节点到生成树的距离int st[N];//节点是否被加入到生成树中int pre[N];//节点的前去节点int n, m;//n 个节点，m 条边void prim(){    memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）    int res= 0;    dt[1] = 0;//从 1 号节点开始生成     for(int i = 0; i > w;//输出边的两个顶点和权重        g[a][b] = g[b][a] = min(g[a][b],w);//存储权重    }    prim();//求最下生成树    //getPath();//输出路径    return 0;}

                Part 2：Kruskal算法求最小生成树

                1.题目描述

                给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

                求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

                给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。

                由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

                输入格式

                第一行包含两个整数 n 和 m。

                接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

                输出格式

                共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

                数据范围

                1≤n≤105,

                1≤m≤2∗105,

                图中涉及边的边权的绝对值均不超过 1000。

                输入样例

                4 51 2 11 3 21 4 32 3 23 4 4

                输出样例

                6

                2.算法

                • prim 算法采用的是一种贪心的策略
                • 将所有边按照权值的大小进行升序排序，然后从小到大一一判断
                • 如果这个边与之前选择的所有边不会组成回路（用并查集判断），就选择这条边分；反之，舍去
                • 直到具有 n 个顶点的连通网筛选出来 n-1 条边为止
                • 筛选出来的边和所有的顶点构成此连通网的最小生成树

                  #include #include #include using namespace std;const int N = 100010;int p[N];//保存并查集struct E{    int a;    int b;    int w;        //通过边长进行排序    bool operator w  n >> m;    for(int i = 1; i  a >> b >>c;        edg[i] = {a, b, c};    }        sort(edg + 1, edg + m + 1);//按边长排序    klskr();        //如果保留的边小于点数-1，则不能连通    if(cnt