二十九、搜索与图论——克鲁斯卡尔算法(Kruskal 算法,稀疏图)

这篇具有很好参考价值的文章主要介绍了二十九、搜索与图论——克鲁斯卡尔算法(Kruskal 算法,稀疏图)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、基本思路

1、基本思想与概念

  • 解决问题:
    • 多个城市中铺公路,使城市之间可以相互联通,问如何才能让铺设公路的长度最短——铺设的路径即为最小生成树。
  • 思想:
    • 从小到大枚举每条边,从小到大试图将每条边假如生成树,只要这条边对应的两个点不在一个集合,则把这条边加到集合中来。
  • 主要面对的是稀疏图的最小生成树问题
  • 使用并查集来进行同一集合的判断。

二十九、搜索与图论——克鲁斯卡尔算法(Kruskal 算法,稀疏图)

2、算法步骤

    1. 将所有边按照权重进行从小到大排序(快排)—— O(mlogn)算法瓶颈
    1. 枚举每一条边 a,b,权重 c
    • if(a, b不连通){
    • 将这条边加入集合中,相当于给 a, b 之间加一条边
    • }

3、注意

  • Kruskal 算法是以边为单位进行遍历,Prim算法是以点为单位进行边的遍历
  • 使用并查集进行“是否在同一个集合”的判断
  • 不需要使用邻接表、邻接矩阵存储图,只需要存边,然后做好排序即可。

二、Java、C语言模板实现

//Java 模板实现
    static int N = 100010;
    static int n,m;
    static int u,v,w;
    
    // 使用并查集判断每个节点的归属集合
    // p代表点 1 ~ n 的父节点是什么
    static int[] p = new int[N];
    
    // 查询节点 x 的根节点(只有根节点才可以满足p[x] = x)
    // 根节点的p[x]代表的就是集合本身编号
    static int findRoot(int x){
        if(p[x] != x){
            p[x] = findRoot(p[x]);      // 并查集中的递归与路径压缩
        }
        return p[x];
    }


        int res = 0;            // 存储最小生成树经过的路程,也就是走过一遍的最小路程数
        int count = 0;          // 记录集合中的边数,之所以增加这个变量,是因为并不能
        
        for(int i = 0; i < n; i++){     // 此处是初始化每个点为一个集合,为了后面合并做准备
            p[i] = i;                   // 满足根节点 p[x] = x 条件
        }
        
        for(int i = 0; i < m; i++){
            u = in.nextInt();
            v = in.nextInt();
            w = in.nextInt();
            
            edges.add(new Edge(u, v, w));       // 将边加入队列中,并做好排序
        }
        
        for(int i = 0; i < m; i++){
            Edge temp = edges.poll();           // 取出首节点,也就是最小的边
            int a = temp.a;
            int b = temp.b;
            int ww = temp.w;
            a = findRoot(a);                    // 找到点a的根节点
            b = findRoot(b);                    // 找到点b的根节点/所在集合
            
            if(a != b){     // 两者没有连通,也就是没有边通路
               p[a] = b;    // 将其中一个集合并入另一个集合
               res += ww;   // 累加两点之间的距离
               count++;     // 判断走过了多少条边
            }
            
        }

class Edge implements Comparable<Edge>{
    
    int a;
    int b;
    int w;
    public Edge(int x,int y, int z){
        this.a = x;
        this.b = y;
        this.w = z;
    }
    
    public int compareTo(Edge other){           // 此处是为了在优先队列中实现排序,也就实现了Comparable接口
        return Integer.compare(this.w, other.w);
    }
}
```cpp
// C++语言实现,此处是yxc实现
int n, m;       // n是点数,m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

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

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通,则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

三、例题题解

二十九、搜索与图论——克鲁斯卡尔算法(Kruskal 算法,稀疏图)文章来源地址https://www.toymoban.com/news/detail-448719.html

// java题解实现
import java.util.*;

public class Main{
    static int N = 100010;
    static int n,m;
    static int u,v,w;
    
    // 使用并查集判断每个节点的归属集合
    // p代表点 1 ~ n 的父节点是什么
    static int[] p = new int[N];
    
    // 查询节点 x 的根节点(只有根节点才可以满足p[x] = x)
    // 根节点的p[x]代表的就是集合本身编号
    static int findRoot(int x){
        if(p[x] != x){
            p[x] = findRoot(p[x]);      // 并查集中的递归与路径压缩
        }
        return p[x];
    }
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        
        // 使用优先队列进行边的存储,在添加过程中实现边添加边排序
        // 当然此处实际上也可以使用 Edge 数组进行存储
        PriorityQueue<Edge> edges = new PriorityQueue<Edge>();
    
        n = in.nextInt();
        m = in.nextInt();
        
        int res = 0;            // 存储最小生成树经过的路程,也就是走过一遍的最小路程数
        int count = 0;          // 记录集合中的边数,之所以增加这个变量,是因为并不能
        
        for(int i = 0; i < n; i++){     // 此处是初始化每个点为一个集合,为了后面合并做准备
            p[i] = i;                   // 满足根节点 p[x] = x 条件
        }
        
        for(int i = 0; i < m; i++){
            u = in.nextInt();
            v = in.nextInt();
            w = in.nextInt();
            
            edges.add(new Edge(u, v, w));       // 将边加入队列中,并做好排序
        }
        
        for(int i = 0; i < m; i++){
            Edge temp = edges.poll();           // 取出首节点,也就是最小的边
            int a = temp.a;
            int b = temp.b;
            int ww = temp.w;
            a = findRoot(a);                    // 找到点a的根节点
            b = findRoot(b);                    // 找到点b的根节点/所在集合
            
            if(a != b){     // 两者没有连通,也就是没有边通路
               p[a] = b;    // 将其中一个集合并入另一个集合
               res += ww;   // 累加两点之间的距离
               count++;     // 判断走过了多少条边
            }
            
        }
        
        if(count != (n - 1)){   // 没有走过 n-1 条边,也就意味着没有全部连接的通路,也就没有最小生成树
            System.out.println("impossible");
        }else{
            System.out.println(res);
        }
    }
    
    
}

class Edge implements Comparable<Edge>{
    
    int a;
    int b;
    int w;
    public Edge(int x,int y, int z){
        this.a = x;
        this.b = y;
        this.w = z;
    }
    
    public int compareTo(Edge other){           // 此处是为了在优先队列中实现排序,也就实现了Comparable接口
        return Integer.compare(this.w, other.w);
    }
}

到了这里,关于二十九、搜索与图论——克鲁斯卡尔算法(Kruskal 算法,稀疏图)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】最小生成树之普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

      🌱博客主页:大寄一场. 🌱系列专栏:数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 一、最小生成树的概念 二、最小生成树的求解方法 三、练习题 四、最小生成树在实际应用中的例子 最近非科班的同学学到了最小生成树并询问我,于是想趁

    2024年02月07日
    浏览(42)
  • 二十一、搜索与图论——拓扑序列(有向图)

    拓扑序列定义: 若一个由图中所有点构成的序列 A满足:对于图中的每条边 (x,y),x在 A中都出现在 y之前,则称 A是该图的一个拓扑序列。 人话: 始终满足每条边的起点在终点前面,从前指向后。 注意:如果在有向图中构成一个环,则必定无法构成拓扑结构,也可以证明有向

    2024年02月04日
    浏览(54)
  • 搜索与图论 - 搜索与图在算法中的应用【中】

    目录 迪杰斯特拉算法Dijkstra  Dijkstra求最短路 I Dijkstra求最短路 II 贝尔曼-福特算法 bellman-ford 有边数限制的最短路 SPFA算法 spfa求最短路  spfa判断负环 Floyd Floyd求最短路   该算法不能存在负权边 思路: 初始化距离数组, dist[1] = 0, dist[i] = inf; for n次循环 每次循环确定一个min加

    2023年04月08日
    浏览(82)
  • 搜索与图论(一)

    DFS不具有最短性 一层一层搜索,可以搜到最短路。       适用于有向图  

    2024年02月15日
    浏览(37)
  • 搜索与图论-拓扑序列

    为什么记录呢 因为不记录全忘了 虽然记了也不一定会看 有向无环图一定有拓扑序列 邮箱无环图 - 拓扑图 入度为0的点作为起点 入度为0的点入队列 枚举出边 t-j 删掉当前边,t-j . j的入度减1 判断j的入度是否为0,来判断是否加入队列 有环: 不存在入度为0的点

    2024年02月11日
    浏览(40)
  • 三、搜索与图论

    树是一种特殊的图 存储可以用链式向前星或者vector 有向无环图也是拓扑图 入度:有多少条边指向自己 出度:有多少条边出去 入度为0就是起点,出度为0就是终点 帮助理解 Dijkstra求最短路 I Dijkstra求最短路 II 增加点权,求有多少条最短路 题目链接 增加边权,求花费最少 题

    2024年02月20日
    浏览(46)
  • 搜索与图论(三)

    朴素版Prim 一般用于稠密图 算法流程: 集合表示当前已经在连通块的点 1.初始化距离,把所有距离都初始化为正无穷 2.n次迭代,找到集合外距离最小的点 -t 3.用t来更新其它点到集合的距离 一般用于稀疏图 算法流程: 1.将所有边按照权重从小到大排序 2.枚举每一条边(a,b),权重为

    2024年02月14日
    浏览(34)
  • 搜索与图论(二)

    所有边权都是正数 朴素Dijkstra算法 基本思路: 从1号点到其他点的最短距离 步骤: 定义一个s集合包含当前已确定最短距离的点 1、初始化距离dis[1] = 0,dis[其它] = 正无穷 2、for i 0-n循环n次      2.1找到不在s中的距离最近的点 -t     2.2把t加到s当中去     2.3用t来更新其它点的距

    2024年02月14日
    浏览(32)
  • 【算法】复习搜索与图论

    🍎 博客主页:🌙@披星戴月的贾维斯 🍎 欢迎关注:👍点赞🍃收藏🔥留言 🍇系列专栏:🌙 蓝桥杯 🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得,但是请相信,世界上总有一些美好值得我们全力以赴,哪怕粉身碎骨!🌙 🍉一起加油,去追寻、去成为更好的自己!

    2024年02月05日
    浏览(46)
  • 搜索与图论:Prim

    每次将离连通部分的最近的点和点对应的边加入的连通部分,连通部分逐渐扩大,最后将整个图连通起来,并且边长之和最小。

    2024年02月08日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包