首页 > 编程语言 >算法模板

算法模板

时间:2024-08-16 16:08:58浏览次数:12  
标签:int ++ 算法 rootY 集合 节点 模板 dis

拓扑排序

点击查看代码
public Boolean bfsOptimize(int n, int[][] edges) {
    // 初始化入度数组,每个节点有两个元素,第一个元素表示入度,第二个元素暂时未使用
    int[][] indegrees = new int[n][2];
    // 初始化邻接表,用于存储图的连接关系
    List<List<Integer>> adj = new ArrayList<>();
    // 遍历所有节点,为每个节点创建一个空的邻接表
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    // 遍历所有边,构建邻接表并更新节点的入度
    for (int i = 0; i < edges.length; i++) {
        int pre = edges[i][1]; // 边的起点
        int next = edges[i][0]; // 边的终点
        adj.get(pre).add(next); // 将终点添加到起点的邻接表中
        // 更新终点的入度
        indegrees[next][0]++;
    }
    // 初始化队列,用于进行广度优先搜索
    Deque<Integer> queue = new LinkedList<>();
    // 将所有入度为0的节点加入队列
    for (int i = 0; i < n; i++) {
        if (indegrees[i][0] == 0) {
            queue.addLast(i);
        }
    }
    // 记录已经访问过的节点数量
    int count = 0;
    // 当队列不为空时,继续搜索
    while (!queue.isEmpty()) {
        int cur = queue.poll(); // 出队一个节点
        System.out.println(cur); // 打印当前节点
        count++; // 访问节点数量加1
        // 遍历当前节点的所有邻接节点
        for (int next : adj.get(cur)) {
            indegrees[next][0]--; // 将邻接节点的入度减1
            // 如果邻接节点的入度变为0,则将其加入队列
            if (indegrees[next][0] == 0) {
                queue.addLast(next);
            }
        }
    }
    // 如果访问过的节点数量等于总节点数,说明可以进行拓扑排序,返回true
    return count == n;
}

并查集

点击查看代码
class Union {
    int n;// 节点数
    int[] p;// 父节点数组,p[i]表示节点i的父节点
    int[] s;// 当前分支大小数组,s[i]表示以节点i为根的集合的大小
    int count;// 连通分量数,即当前有多少个独立的集合

    //初始化
    public Union(int n) {
        //注意事项:节点从0开始
        // 注意事项:节点从0开始
        this.n = n; // 将传入的参数n赋值给类的成员变量n,表示集合的大小
        p = new int[n]; // 创建一个长度为n的数组p,用于存储每个节点的父节点
        s = new int[n]; // 创建一个长度为n的数组s,用于存储以当前节点为根的集合的大小
        count = n; // 初始化连通分量的数量为n,即每个节点初始时都是一个独立的集合
        for (int i = 0; i < n; i++) { // 遍历所有节点
            p[i] = i; // 将节点i的父节点设置为其自身,表示每个节点初始时都是自己的父节点
            s[i] = 1; // 将节点i所在集合的大小设置为1,因为每个节点初始时都是一个独立的集合
        }
    }
    public int find(int x){
        // 如果节点x的父节点是它自己,说明x就是根节点,直接返回x
        if(x==p[x])
            return x;
        else{
            // 如果节点x的父节点不是它自己,递归查找其父节点的根节点
            p[x] = find(p[x]);
            // 路径压缩,将x的父节点直接设置为找到的根节点,优化后续查找操作
            return p[x];
        }
    }

    public void union(int x,int y){
        // 查找节点x的根节点
        int rootX = find(x);
        // 查找节点y的根节点
        int rootY = find(y);
        // 如果x和y的根节点相同,说明它们已经在同一个集合中,无需合并
        if (rootX == rootY)
            return;
        // 如果x的根节点所在集合的大小大于y的根节点所在集合的大小
        if (s[rootX] > s[rootY]) {
            // 将y的根节点的父节点设置为x的根节点,实现合并
            p[rootY] = rootX;
            // 更新x的根节点所在集合的大小,加上y的根节点所在集合的大小
            s[rootX] += s[rootY];
        } else {
            // 如果y的根节点所在集合的大小大于等于x的根节点所在集合的大小
            // 将x的根节点的父节点设置为y的根节点,实现合并
            p[rootX] = rootY;
            // 更新y的根节点所在集合的大小,加上x的根节点所在集合的大小
            s[rootY] += s[rootX];
        }
        // 合并后,连通分量的数量减1
        count--;
    }
    // 获取最大分支节点个数
    public int getMaxCount(){
        int max=0; // 初始化最大分支节点个数为0
        for(int i=0;i<n;i++){ // 遍历所有节点
            max=Math.max(max,s[i]); // 更新最大分支节点个数,取当前最大值与节点i所在集合大小的较大值
        }
        return max; // 返回最大分支节点个数
    }
    // 获取连通分量个数
    public int getCount(){
        return count; // 直接返回连通分量个数
    }

}

Flody算法

点击查看代码
 	/**
     * 弗洛伊德算法:任意两点之间最短距离
     */
    public void floyd() {

        //对中间顶点遍历
        for (int k = 0; k < dis.length; k++) {
            //从i顶点开始出发
            for (int i = 0; i < dis.length; i++) {
                //到达j顶点
                for (int j = 0; j < dis.length; j++) {
                    //求出从i顶点出发经过k到达j的距离
                   if(dis[i][k] + dis[k][j] < dis[i][j]) {
                       //更新距离
                       dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }

标签:int,++,算法,rootY,集合,节点,模板,dis
From: https://www.cnblogs.com/life1314/p/18363029

相关文章

  • 基于协同过滤推荐算法+springboot+vue的篮球球队网站
    博主主页:猫头鹰源码博主简介:Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万+、专注Java技术领域和毕业设计项目实战,欢迎高校老师\讲师\同行交流合作​主要内容:毕业设计(Javaweb项目|小程序|Python|HTML|数据可视化|SSM|SpringBoot|Vue|Jsp|PHP......
  • 掌握一致性哈希算法
    如何分配请求?大多数网站背后肯定不是只有一台服务器提供服务,因为单机的并发量和数据量都是有限的,所以都会用多台服务器构成集群来对外提供服务。但是问题来了,现在有那么多个节点(后面统称服务器为节点,因为少一个字),要如何分配客户端的请求呢?其实这个问题就是「负载均衡问......
  • C/C++算法概述
    摘要1.性能优势:C/C++语言以其接近硬件的特性而著称,提供了对底层硬件的直接控制能力。这意味着算法可以实现更高的执行效率,特别是在需要处理大量数据或实时性能要求较高的场景中。2.灵活性:C/C++提供了丰富的数据结构和操作,允许开发者以灵活的方式实现复杂的算法。同时,C++的......
  • 红温刷算法题(C/C++)
    此文章主要是给刷算法题的小萌新写的题解,博主每日刷题,把所刷的题以及所获都会发到博客里面,文章有详解思路,并且有对应的AC代码,希望我的博客对算法小萌新有所帮助。感谢CSDN平台给我这个机会,我会努力创作,创作高质量文章。 P1002[NOIP2002普及组]过河卒题目描述棋盘上 A ......
  • 《机器学习》 KNN算法、数据可视化 No.1
    一、了解机器学习1、什么是机器学习        机器学习是一种人工智能(AI)的分支,旨在让计算机通过数据自动学习和改进。机器学习算法被设计用于从数据中提取模式和规律,然后利用这些模式和规律来做出预测或做出决策,而无需明确的程序指令。        机器学习的基本......
  • 看demo学算法之 循环神经网络(RNN)
    今天我们来聊聊神经网络中的“记忆大师”——循环神经网络(RNN)。想象一下,你正在看电影,每一帧都连贯着前一帧的故事情节。RNN就像是这样一位观众,它能记住之前看到的内容,帮助理解当前的画面。是不是很酷?......
  • 【Python SHA256 摘要算法】
    SHA256是一种广泛使用的密码散列函数,用于生成数据的唯一指纹,即散列值。它属于SHA-2家族,该家族还包括SHA-384和SHA-512算法。SHA256算法在许多领域都有应用,例如:数据完整性验证:用于验证数据在传输或存储过程中是否被篡改。例如,在下载软件时,通常会提供软件的SHA256哈......
  • 数据结构与算法详解
    目录一、引言二、数据结构1.数组(Array)定义特点应用场景总结表格2.链表(LinkedList)定义特点应用场景总结表格3.栈(Stack)定义特点应用场景总结表格4.队列(Queue)定义特点应用场景总结表格5.树(Tree)定义特点应用场景总结表格6.哈希表(HashTable)定......
  • Day31 贪心算法part5
    目录任务56.合并区间思路738.单调递增的数字思路968.监控二叉树思路任务56.合并区间以数组intervals表示若干个区间的集合,其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。思路......
  • 《密码保护升级指南:顶级哈希算法大比拼》
    密码哈希技术深度剖析:掌握MessageDigest、Bcrypt与PBKDF2一、为何探究密码哈希技术随着互联网的发展,网络安全变得越来越重要。密码哈希算法作为保护用户密码安全的关键技术之一,其重要性不言而喻。在数字时代,密码安全构成了保护用户隐私和资产的第一道防线。密码哈......