最小生成树Prim + Kruskal

🕗 发布于 2024-02-29 11:22 java 算法

最小生成树

最小生成树仅仅针对无向图

是否成环

参考链接
这里直接用carl给的模板

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

通过模板，我们可以知道，并查集主要有三个功能。

寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点

一个误区

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    if (isSame) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

这里不能直接将isSame抽象出来，在join里面调用，必须寻根以后再father[v] = u;

寻根以后的u v 和 join传入的参数u v 是不一样的！！！

并查集只能判断无向图是否成环

public class test4 {

    public static int n;
    public static int[] father;

    public void init() {
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    public int find(int u) {
        if (u == father[u]) {
            return u;
        } else
            return father[u] = find(father[u]);
    }

    public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }

    public void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return;
        father[v] = u;
    }

    public static void main(String[] args) {
        test4 t = new test4();
        test4.n = 4;
        t.init();

        t.join(1, 2);
        t.join(2, 3);
        t.join(1, 3);

        System.out.println(Arrays.toString(father));
        System.out.println(t.isSame(1, 3));
    }
}

通过这个例子可以看到，t.join(1, 3);还是t.join(3, 1); 最后判断t.isSame(1, 3)都会是true

在这里插入图片描述

最小生成树参考视频

Kruskal

Kruskal.java

import java.util.*;

class Edge implements Comparable<Edge> {
    int from, to, weight;

    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

public class Kruskal {
    public static int find(int[] parent, int u) {
        if (u == parent[u]) {
            return u;
        }else{
            return parent[u] = find(parent, parent[u]);
        }
    }

    public static void union(int[] parent, int u, int v) {
        u = find(parent, u);
        v = find(parent, v);
        if(u==v) return;
        parent[u] = v;
    }

    public static List<Edge> kruskalMST(List<Edge> edges, int n) {
        Collections.sort(edges);

        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
// 最小生成树的边
        List<Edge> result = new ArrayList<>();
        for (Edge edge : edges) {
            int u = find(parent, edge.from);
            int v = find(parent, edge.to);
            // 成环了就跳过
            if (u != v) {
                result.add(edge);
                union(parent, u, v);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // n 代表顶点的个数
        int n = 4;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));

        List<Edge> mst = kruskalMST(edges, n);

        for (Edge edge : mst) {
            System.out.println(edge.from + " - " + edge.to + ": " + edge.weight);
        }
    }
}

结果

在这里插入图片描述

Prim

普通写法

Prim.java

public class Prim {
    public static void main(String[] args) {
        // int[][] graph = {
        // {0, 2, 0, 6, 0},
        // {2, 0, 3, 8, 5},
        // {0, 3, 0, 0, 7},
        // {6, 8, 0, 0, 9},
        // {0, 5, 7, 9, 0}
        // };
        int[][] graph = {
                { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                { 0, 0, 2, 0, 0, 0, 6, 7, 0 },
        };

        int[] parent = prim(graph);

        // 打印最小生成树的边
        for (int i = 1; i < parent.length; i++) {
            System.out.println("parent["+i+"]="+parent[i] );
        }
    }

    public static int[] prim(int[][] graph) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        int[] parent = new int[n];
        int[] key = new int[n];

        // 初始化距离数组和父节点数组
        for (int i = 0; i < n; i++) {
            key[i] = Integer.MAX_VALUE;
            parent[i] = -1;
        }
        key[0] = 0;

        // Prim 算法
        for (int i = 0; i < n; i++) {
            int u = -1;
            // 这个for是为了找出当前最近的节点，并标记为已访问
            for (int j = 0; j < n; j++) {
                if (!visited[j] && (u == -1 || key[j] < key[u])) {
                    u = j;
                }
            }

            visited[u] = true;

            // 这个for是为了看那些没有被访问过的节点，更新他们的距离
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0 && graph[u][v] < key[v]) {
                    key[v] = graph[u][v];
                    parent[v] = u;
                }
            }
        }

        return parent;
    }
}

最小生成树的结果不唯一

上述代码的运行结果为

在这里插入图片描述
另外一种树为，权值和均为37

在这里插入图片描述

优先级队列的写法

Prim2.java

import java.util.PriorityQueue;

public class Prim2 {
    public static void main(String[] args) {
        int[][] graph = {
                { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                { 0, 0, 2, 0, 0, 0, 6, 7, 0 },
        };

        int[] parent = prim(graph);

        // 打印最小生成树的边
        for (int i = 1; i < parent.length; i++) {
            System.out.println("parent[" + i + "]=" + parent[i]);
        }
    }

    public static int[] prim(int[][] graph) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        int[] parent = new int[n];
        int[] key = new int[n];

        // 初始化距离数组和父节点数组
        for (int i = 0; i < n; i++) {
            key[i] = Integer.MAX_VALUE;
            parent[i] = -1;
        }
        key[0] = 0;

        // 使用优先队列存储待处理的顶点
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < n; i++) {
            pq.offer(new int[] { key[i], i });
        }

        // Prim 算法
        while (!pq.isEmpty()) {
            int[] minNode = pq.poll();
            int u = minNode[1];
            visited[u] = true;

            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0 && graph[u][v] < key[v]) {
                    key[v] = graph[u][v];
                    parent[v] = u;
                    pq.offer(new int[] { key[v], v });
                }
            }
        }

        return parent;
    }
}

优先级队列的思想还是比较容易理解的，刚好其输出是另外一颗最小树，也刚好验证了上面的说法

在这里插入图片描述

原文地址：https://blog.csdn.net/qq_40896190/article/details/136348406

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：nextcloud 基础维护
下一篇：Redis数据类型和使用场景

嵌入式C语言自我修养：GNU C编译器扩展语法精讲
)(void)是一个类型转换，它将后面的表达式转换为void类型，这意味着表达式的结果被丢弃。而是一个比较两个变量地址是否相同的表达式，这个表达式的结果是一个布尔值，但通过将其转换为void类型，这个
阅读更多2024-09-22
详细解析：在 Windows 上使用动态链接库（DLL）的关键方面
上述段落详细阐述了在 Windows 系统上使用动态链接库（DLL）的关键方面，涵盖了DLL的文件类型和扩展、导出控制、运行时依赖，以及导入库的使用。这些内容对于确保 DLL 的正确创建、管理和使用至
阅读更多2024-09-22
2024年中国研究生数学建模竞赛C题——解题思路
2024年中国研究生数学建模竞赛C题——解题思路，关注公众号，回复“2024研赛C题”，获取更多思路、源程序、数据分析等相关资源。
阅读更多2024-09-22
MySQL：事务隔离级别
本文主要介绍MySQL的事务隔离级别
阅读更多2024-09-22
数字化企业的绿色增长与业务模式创新：技术变革中的可持续发展路径
例如，企业可以通过回收和再利用资源，减少对原材料的依赖，从而实现生产的可持续性。通过与其他企业的合作，企业能够共享资源，减少生产和物流中的碳排放。实现的绿色增长，不仅能够提高企业的运营效率，还能够帮助
阅读更多2024-09-22
智谱清影 - CogVideoX-2b-部署与使用
🍑个人主页：Jupiter.🚀 所属专栏：Linux从入门到进阶。
阅读更多2024-09-22
JFreeChart
JfreeChart是用Java开发的开源库，它可以在基于Java的应用程序可用于创建各种各样的图表。通过使用JFreeChart，可以创建2D和3D图表，如饼图，条形图，折线图，XY图和3D图表所有
阅读更多2024-09-22
如何设计可靠的 IIoT 架构
在 IIoT 设计中定义业务层可在 IIoT 网络的运作方式与实现这些目标的方式之间建立具体的联系。您的网络层是 IIoT 架构的一部分，它允许设备层与网络的其余部分进行通信。实现层包括 IIoT 架
阅读更多2024-09-22
[Unity Demo]从零开始制作空洞骑士Hollow Knight第七集：制作小骑士完整的冲刺Dash行为
大家又好久不见（虽然就过了半天）这期我决定继续完善小骑士的行为，上一期我们实现了小骑士完整的跳跃降落行为，这一期我们就来做小骑士的冲刺行为，这其中涉及到素材的导入，创建tk2dSprite和tk2dS
阅读更多2024-09-22
力扣 18.四数之和
思路和 15. 三数之和一样，排序后，枚举 nums[a] 作为第一个数，枚举 nums[b] 作为第二个数，那么问题变成找到另外两个数，使得这四个数的和等于 target，这可以用双指针解决。a
阅读更多2024-09-22

最小生成树Prim + Kruskal

最小生成树

是否成环

并查集只能判断无向图是否成环

Kruskal

Prim

普通写法

优先级队列的写法

相关文章