精华内容
下载资源
问答
  • 环检测算法
    万次阅读
    2020-09-23 10:01:52

    简介

    环检测应该是一个非常常见的算法问题,怎么判断是否有环的问题呢?

    一个很简单的做法就是用HashSet来保存要遍历的数据,如果出现了重复就知道这个链表是有环的。但是这个方法需要保存遍历过的所有的元素,所以其空间复杂度是o(n)。

    有没有什么方法可以不用保存之前的元素也能够判断是否有环呢?

    来看看弗洛伊德的兔子和乌龟算法吧。

    弗洛伊德简介

    有的同学会说了,弗洛伊德(Sigmund Freud)谁不知道,梦的解析的作者,大名鼎鼎的心理学专家,精神分析学派的创始人。

    但是这里我们讲的弗洛伊德全名是Robert W.Floyd(罗伯特·弗洛伊德)而不是Sigmund Freud。

    罗伯特·弗洛伊德是计算机科学家,图灵奖得主,前后断言法的创始人,堆排序算法和Floyd-Warshall算法的创始人之一。

    它获得了1978年图灵奖,是一位“自学成才的计算机科学家”。

    这个兔子和乌龟算法就是他发明的一种环检测算法。

    构造一个环

    更多相关内容
  • 环检测算法 给定一个图,判断图中是否存在环,可以使用dfs求解,根据图的类型可以分为两种类型: (1)无向图判断是否有环; (2)有向图判断是否有环。 1. 无向图环检测算法 分析 使用st数组记录在...

    环检测算法

    • 给定一个图,判断图中是否存在环,可以使用dfs求解,根据图的类型可以分为两种类型:

      • (1)无向图判断是否有环;

      • (2)有向图判断是否有环。

    1. 无向图环检测算法

    分析

    • 使用st数组记录在深度遍历的过程中是否存在点之前已经被遍历过,如果存在,说明存在环。

    • 注意为了消除无向边的影响,递归的过程中需要传入每个点的父节点fa

    代码

    • C++
    /* 测试用例
    3 3
    1 2
    2 3
    3 1
    */
    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int N = 100010, M = N * 2;
    
    int n, m;
    int h[N], e[M], ne[M], idx;
    bool st[N];
    
    void add(int a, int b) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // 有环的返回true
    bool dfs(int u, int fa) {
        
        st[u] = true;
        
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            
            if (st[j] || dfs(j, u)) return true;
        }
        return false;
    }
    
    int main() {
        
        cin >> n >> m;
        memset(h, -1, sizeof h);
        while (m--) {
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
        }
        
        bool flag = false;
        for (int i = 1; i <= n; i++)
            if (!st[i] && dfs(i, -1)) {
                flag = true;
                break;
            }
        
        if (flag) puts("YES");
        else puts("NO");
        
        return 0;
    }
    

    2. 有向图环检测算法

    方法一

    分析

    • 有向图不同于无向图,不能使用无向图的方式判断是否有环,因为即使遍历到了之前遍历过的点,也不能确定有环,如下图:

    在这里插入图片描述

    • 从上图可以看出,两次递归路径会遍历到同一个点,即编号为6的点,但是因为是有向图,因此没有环。

    • 使用st数组记录每个点是否在之前遍历过,同时使用path数组记录当前在递归路径上的点,如果遍历到path上的点,说明存在环;否则如果当前遍历的点不再path上且sttrue的话,则之后的递归路径上不会存在环,返回false即可;否则继续递归遍历。

    代码

    • C++
    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int N = 100010, M = N * 2;
    
    int n, m;
    int h[N], e[M], ne[M], idx;
    bool st[N], path[N];
    
    void add(int a, int b) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // 有环的返回true
    bool dfs(int u) {
        
        st[u] = true;
        path[u] = true;
        
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            
            if (path[j]) return true;
            if (st[j]) return false;
            
            if (dfs(j)) return true;
        }
        
        path[u] = false;
        
        return false;
    }
    
    int main() {
        
        cin >> n >> m;
        memset(h, -1, sizeof h);
        while (m--) {
            int a, b;
            cin >> a >> b;
            add(a, b);
        }
        
        bool flag = false;
        for (int i = 1; i <= n; i++)
            if (!st[i] && dfs(i)) {
                flag = true;
                break;
            }
        
        if (flag) puts("YES");
        else puts("NO");
        
        return 0;
    }
    

    方法二

    分析

    • 可以使用拓扑排序判断有向图中是否存在环,只需要判断是否所有点都入队即可。

    • 如果所有点都入过队,则说明存在拓扑序,因此不存在环;否则存在环。

    代码

    • C++
    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int N = 100010, M = N * 2;
    
    int n, m;
    int h[N], e[M], ne[M], idx;
    int d[N], q[N];
    
    void add(int a, int b) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    bool topsort() {
        
        int hh = 0, tt = -1;
        for (int i = 1; i <= n; i++)
            if (d[i] == 0)
                q[++tt] = i;
        
        while (hh <= tt) {
            int t = q[hh++];
            
            for (int i = h[t]; ~i; i = ne[i]) {
                int j = e[i];
                if (--d[j] == 0) q[++tt] = j;
            }
        }
        
        return tt != n - 1;  // 不是所有点如果队,则存在环
    }
    
    int main() {
        
        cin >> n >> m;
        memset(h, -1, sizeof h);
        while (m--) {
            int a, b;
            cin >> a >> b;
            d[b]++;
            add(a, b);
        }
        
        if (topsort()) puts("YES");
        else puts("NO");
        
        return 0;
    }
    
    展开全文
  • 2022.3.23 图论——环检测算法

    千次阅读 2022-03-23 19:53:44
    课程表I(环检测算法


    一、今日刷题

    1.题目

    1. 课程表

    跳转LeetCode

    你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。

    在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。

    例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。
    请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。

    示例 1:
    输入:numCourses = 2, prerequisites = [[1,0]]
    输出:true
    解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。

    示例 2:
    输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
    输出:false
    解释:总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。


    2.分析

    参考文章

    一上来读题都有点没读懂,看过分析后才理解,题目中给的 numCourses 并不是限制条件,反而在做题中会作为声明的数组长度的数值,为我们提供帮助。真正起限制作用的是二维数组 prerequisites,该数组中存储着每门课程的前置课程,当我们所选的课程与某门课程形成互为前置课程的关系时,会导致无法完成所有课程的学习。

    我们采用图结构来解决此问题,因此,题目转化为:判断以所有课程为节点生成的图中是否存在环。

    在编码层面,问题则转化为:由所给数组构建图 → 图的遍历 → 判断图中是否存在环

    ①构建图:
    以邻接表形式存储图,

    List<Integer>[] graph = new LinkedList[numCourses];
    

    邻接表本质上是由List集合元素组成的数组,为每个图节点创建一个集合,所以数组的长度为 numCourses。
    将课程填入其前置课程的邻接表中(其实不太符合正规逻辑,我们通常想的是,学习某课之前需要学习其前置课程,所以将前置课程加入该课程的邻接表中),这样就形成了由前置课程指向课程的有向边。将 numCourses 个集合组织起来,就形成了图。

    graph[preCourse].add(course);
    

    ②图的遍历 + 判断图中是否存在环:
    我们将这两个步骤一起处理。和找图中的所有路径一样,维护两个数组,

    boolean[] onPath;
    boolean[] visited;
    

    在这里插入图片描述
    visited 中被标记为 true 的节点用灰色表示,在 onPath 中被标记为 true 的节点用绿色表示

    类比贪吃蛇游戏,visited 记录蛇经过过的格子,而 onPath 仅仅记录蛇身。onPath 用于判断是否成环,类比当贪吃蛇自己咬到自己(成环)的场景

    3.代码

    答案代码:

    package Graph;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * @author: LYZ
     * @date: 2022/3/23 19:28
     * @description: 207. 课程表
     */
    public class CanFinish {
        public static void main(String[] args) {
            int numCourses = 2;
            int[][] prerequisites = {{0, 1}};
            CanFinish canFinish = new CanFinish();
            boolean ans = canFinish.canFinish(numCourses, prerequisites);
            System.out.println(ans);
        }
    
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    
            visited = new boolean[numCourses];
            onPath = new boolean[numCourses];
    
            for (int i = 0; i < numCourses; i++) {
                traverse(graph, i);
            }
            return hasCycle == true ? false : true;
        }
    
        List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
            //创建邻接表存储图
            List<Integer>[] graph = new LinkedList[numCourses];
            //对数组(graph)进行初始化
            for (int i = 0; i < numCourses; i++) {
                graph[i] = new LinkedList<>();
            }
    
            for (int[] edge : prerequisites) {
                //提取课程及其先修课程
                int course = edge[0];
                int preCourse = edge[1];
                //为课程以及先修课程创建联系,即创建由先修课程指向课程的有向边
                graph[preCourse].add(course);
            }
            return graph;
        }
    
        boolean[] visited;
        boolean[] onPath;
        boolean hasCycle = false;
        void traverse(List<Integer>[] graph, int s) {
            if (onPath[s]) {
                hasCycle = true;
            }
            if (visited[s] || hasCycle) {
                return;
            }
    
            visited[s] = true;
            onPath[s] = true;
            for (int n : graph[s]) {
                traverse(graph, n);
            }
            onPath[s] = false;
        }
    }
    

    BFS算法:

    1、构建邻接表,和之前一样,边的方向表示「被依赖」关系。

    2、构建一个 indegree 数组记录每个节点的入度,即 indegree[i] 记录节点 i 的入度。

    3、对 BFS 队列进行初始化,将入度为 0 的节点首先装入队列。

    4、开始执行 BFS 循环,不断弹出队列中的节点,减少相邻节点的入度,并将入度变为 0 的节点加入队列。

    5、如果最终所有节点都被遍历过(count 等于节点数),则说明不存在环,反之则说明存在环。

    // 主函数
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 建图,有向边代表「被依赖」关系
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        // 构建入度数组
        int[] indgree = new int[numCourses];
        for (int[] edge : prerequisites) {
            int from = edge[1], to = edge[0];
            // 节点 to 的入度加一
            indgree[to]++;
        }
    
        // 根据入度初始化队列中的节点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indgree[i] == 0) {
                // 节点 i 没有入度,即没有依赖的节点
                // 可以作为拓扑排序的起点,加入队列
                q.offer(i);
            }
        }
    
        // 记录遍历的节点个数
        int count = 0;
        // 开始执行 BFS 循环
        while (!q.isEmpty()) {
            // 弹出节点 cur,并将它指向的节点的入度减一
            int cur = q.poll();
            count++;
            for (int next : graph[cur]) {
                indgree[next]--;
                if (indgree[next] == 0) {
                    // 如果入度变为 0,说明 next 依赖的节点都已被遍历
                    q.offer(next);
                }
            }
        }
    
        // 如果所有节点都被遍历过,说明不成环
        return count == numCourses;
    }
    
    
    // 建图函数
    List<Integer>[] buildGraph(int n, int[][] edges) {
        // 见前文
    }
    
    展开全文
  • 虹膜钠环检测算法.docx
  • 针对光纤陀螺敏感线圈(光纤)制备过程中,光纤的绕制张力变化和光纤承载主轴跳动度变化等因素导致的"爬丝"和"间隙"绕制缺陷,提出基于区域的光纤环绕制缺陷检测算法,将原始光纤凹凸特征的处理转换成矩形大小及数量...
  • 判断负环算法

    2021-07-17 20:36:02
    有两种计算方法,都是基于Bellman-Ford算法或者SPFA算法。 第一种算法是:统计每个点的入队次数,如果某个点入队大于等于n次,则说明有负 第二种算法是:统计到某个点的最短路所经过点的个数,如果经过n个点,...
    1. 负环的定义
      负环是指权值和为负数的环。负环会使图的最短路径计算陷入死循环,因此,存在负环的图不存在最短路。

    2. 负环的计算方法:
      负环有两种计算方法,都是基于Bellman-Ford算法或者SPFA算法。
      第一种算法是:统计每个点的入队次数,如果某个点入队大于等于n次,则说明有负环
      第二种算法是:统计到某个点的最短路所经过点的个数,如果经过n个点,则说明存在负环。
      (一般情况下,我们使用第二种算法)
      由于当负环存在时,SPFA会陷入死循环,且n是非死循环的最坏情况。所以以上两种算法是正确的。

    3. 求负环算法的编程实现
      首先将所有点的距离都赋值为0
      然后将所有的点入队。
      下面说明这两步的正确性:
      在这里插入图片描述
      算法的复杂度分析:
      SPFA算法的理论复杂度为O(m),但是在实际求负环中算法的复杂度接近O(mn)。这种算法复杂度是比较高的。但是,经验来看,当SPFA的复杂度比较高时,图中大概率存在负环。
      当所有点的入队次数和超过2n时,就认为图中大概率存在负环。

    展开全文
  • 用 Python 实现的 7 个 ECG 心跳检测算法的集合。与新的心电图数据库一起开发
  • 针对已有的数学形态学边缘检测算法对彩色噪声图像检测到的彩色边缘信息不够完整、清晰,提出了一种基于HSI色彩空间的多尺度多结构元的数学形态学边缘检测算法,采用以尺度和结构两个单位元素进行横向和纵向的拓展,...
  • 链表环检测算法

    千次阅读 2016-07-14 16:50:59
    对于链表环检测问题可以使用”龟兔赛跑”算法来进行判断:即使用两个指针,一个指针为快指针(兔)一次移动两步,而另一个指针为慢指针(龟)一次移动一步。如果这个链表有环的话,那么这两个指针一定会在环上的某一点...
  • 单链表的环检测算法

    千次阅读 2014-01-17 20:12:42
    该文中先列举了多种错误的做法,在最后给出了两种正确的算法之前还给出了一种...第一种算法是 Floyd 环检测算法,也被形象的称为“龟兔赛跑算法”。因为使用了两个迭代指针,都从表头开始遍历,其中一个每步进一次另一
  • 针对CT体数据的多尺度特征点检测计算量大、耗时长的问题,提出一种三维中心环绕特征快速检测算法。设计三维中心环绕特征检测子,结合三维积分图像快速生成图像的尺度空间,同时利用三维Harris边缘判定准则去除边缘点...
  • 最近写leetcode 287时,接触到了“龟兔赛跑算法”,搜索了很多文章,终于透彻地理解,现在用最通俗易懂的方法记录一下: 判断是否有的关键思想是:定义两个指针,指针都在开始,一个指针走得快叫fast指针,一个...
  • 基于字符串模式匹配算法的病毒感染检测问题——C语言实现。
  • 为了提高图像纹理检测的效果,采用多阶环形结构量子算法。建立了量子多阶环形结构,每个量子不仅可以与自身沟通,还可以与不同阶的沟通,每个量子可以选择自身左右相连的两个量子作为邻居,也可以在相邻上随机...
  • 总结,以上就是有向图有环,无环检测算法的基本思想。关于有向图有环判断检测的java版源码请参考github之spark文件夹中的directedCycle类(代码参考princeton源码)。 结语 感谢您的观看,如有不足之处,欢迎...
  • 模块次序表、代数及其检测算法

    千次阅读 2022-01-23 11:30:03
    模块次序表的定义,代数环简介与simucpp中的代数环检测算法,直通模块与端点模块的定义等。
  • 解体思路:通过深度优先搜索的方法从每个节点开始分别对图进行遍历,同时进行标记,当检测到已经被标记过的节点时,说明图里有。为了降低时间复杂度,如果某点不在环中,则对其进行置位,这样下次再遍历到它的时候...
  • 提出了一种改进的角点检测算法。本着好的算法不依赖于人为干涉的思想,在 SUSAN算子基础上,通 过对图像灰度值和对比度分析,提出灰度阈值 t和比较函数 C的快速自适应选取。针对 SUSAN算法中对某些 特殊型角点检测会...
  • 缺陷检测,是各行业产品质量管理体系中的重要一,也是产品在正式投入市场应用前最后一道屏障。由于产品可能出现的品质问题多种多样,没有统一的衡量标准,所以一直以来,产品质检都是依靠人工来完成。可以说,产品...
  • 异常检测算法

    千次阅读 2021-10-24 19:41:14
    异常检测算法分类及经典模型概览 - 知乎 维基百科:在数据挖掘中,异常检测(英语:anomaly detection)对不符合预期模式或数据集中其他项目的项目、事件或观测值的识别。 通常异常项目会转变成银行欺诈、结构缺陷...
  • 为了解决现有角点检测算法普遍存在计算时间长、效率不高、不适于实时在线检测的问题,提出了一种基于模糊ID3决策树的快速角点检测算法。利用半径为3像素的 Bresenham圆环作为检测模板,在被检测图像上移动,圆环中心...
  • 在本文中我们展示 在人类视觉中一种有效的色彩外观模型, 其中也包含原则性的参数选择作为一种先天的空间联合机制,可以被推广 以获得优于最新技术的显着性模型楷模。尺度积分是通过逆小波变换实现的 ...
  • Python微信订餐小程序课程...Floyd Cycle Detection Algorithm,即 Floyd 循环检测算法,又称快慢指针法、龟兔指针法。该算法用于判断链表是否存在,以及判断的起点与长度的算法。 算法原理 该算法基于两个指针,

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 52,465
精华内容 20,986
关键字:

环检测算法