【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS)

这篇具有很好参考价值的文章主要介绍了【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 什么是有向图

有向图(Directed Graph),也被称为有向图形或方向图,是一种图的类型。在有向图中,图中的边具有方向,从一个顶点指向另一个顶点。

在有向图中,每个顶点表示一个实体,而有向边则表示实体之间的关系或连接。这种有方向性的边表明了连接的起点和终点之间的单向关系。因此,有向图中的边具有起点和终点的概念,它们不能逆转方向。

与有向图对应的是无向图(Undirected Graph),在无向图中,边是没有方向的,可以双向移动。相比之下,有向图更适合描述具有明确方向性的关系,例如有向的路径、进程之间的依赖关系等。

有向图可以用来解决许多问题,如拓扑排序、最短路径、网络流等。它在计算机科学、图论、网络分析等领域都有广泛的应用。

【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS),数据结构,宽度优先,数据结构,dfs,bfs,图搜索

2. 什么是拓扑排序

拓扑排序(Topological Sort)是对有向无环图(DAG)进行排序的一种算法。它将有向图的所有顶点排列成线性序列,使得对于任何的有向边 (u, v),顶点 u 都在序列中排在顶点 v 的前面。

拓扑排序的应用场景通常涉及到任务或事件之间的依赖关系,其中每个顶点表示一个任务或事件,有向边表示依赖关系。通过拓扑排序,可以确定这些任务或事件的执行次序,以满足依赖关系的约束。

拓扑排序算法的实现过程如下:

  1. 找到没有前置依赖的顶点,即入度为0的顶点,并将其加入结果序列中。
  2. 图中删除该顶点及其相关的边,即更新其他顶点的入度
  3. 重复步骤1和步骤2,直到图中所有顶点都被添加到结果序列中,或者无法找到入度为0的顶点为止
  4. 如果图中存在环路,则无法进行拓扑排序(或者排序得到的数组集合不等于节点总数),因为环路意味着存在循环依赖。

拓扑排序可以通过深度优先搜索(DFS)或广度优先搜索(BFS)来实现。其中,DFS算法更常用,它可以按照深度优先的顺序遍历图,并在遍历完成后逆序得到拓扑排序结果。

拓扑排序的时间复杂度为O(V+E),其中V和E分别是图中的顶点数和边数。

2. 有向图的拓扑排序

例如有向图:[[1,0],[2,0],[3,1],[4,3],[4,2],[5,4]] 数组后面的元素指向前面的元素
【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS),数据结构,宽度优先,数据结构,dfs,bfs,图搜索

2. 1 BFS 广度优先

  • 广度优先搜索需要依赖一个节点的入度数组如下:(当然这里节点也作为数组下标,如果节点和下标不能一一对应,可以使用一个map哈希表去记录下节点与入度的映射表)

【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS),数据结构,宽度优先,数据结构,dfs,bfs,图搜索

  • 然后还需要准备一个节点指向集合,记录节点与节点的指向关系(后续依照这个指向将被指向的节点的入度做减一操作)
    【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS),数据结构,宽度优先,数据结构,dfs,bfs,图搜索
  • 最后就是准备一个队列,队列中依次加入入度为0 的节点,并且队列的出队顺序即为
  • 再根据节点指向集合,若被指向的节点入度为0,那么此时把入度为0的节点加入到队列循环,直到没有入度为0 的节点

模板代码:

      public int[] findOrder(int numCourses, int[][] prerequisites) {
      
      int[] cou = new int[numCourses];//节点入度数组

      int[] num  = new int[numCourses];//用于存储拓扑排序

      List<List<Integer>> couList = new ArrayList<>();//指向与被指向的集合映射

      Queue<Integer> queue = new LinkedList<>();//辅助队列 用于处理入度为0 的节点

      for(int i = 0 ;i<numCourses ;i++)//给集合中节点与被指向节点初始化集合
          couList.add(new ArrayList<Integer>());
    
      for(int[] pre : prerequisites){
        cou[pre[0]]++;//统计各节点的入度
        couList.get(pre[1]).add(pre[0]);//给集合中父节点设置指向子节点的子集合
      }

      for(int i = 0 ;i<numCourses ;i++){
        if(cou[i] == 0) queue.offer(i);//搜索第一个入度为0 的节点  加入队列
      }
      int i = 0;//用于将拓扑排序加入到一个数组用的下标
      while(!queue.isEmpty()){
            int ids = queue.poll();
            numCourses--;//取出一个元素  就让节点总数-1
            num[i] = ids;//拓扑排序 取出的元素加入到数组
            for(int cur : couList.get(ids)){//  couList.get(ids) 根据节点  取出父节点指向的子节点  让被指向的子节点入度 -1
                if(cou[cur] >= 1 ) cou[cur]--;
                if(cou[cur] == 0 ) queue.offer(cur);//若当前节点入度为0  则加入队列
            }
            i++;
      }
      if(numCourses == 0)  return num;
      // 若 numCourses(节点总数) 不等于0说明 说明最后还有入度不为0的节点,没有被处理,说明有环,则无拓扑排序
      // 或者如果拓扑排序数组num的长度 不等于节点总数 说明拓扑排序不完整,说明无拓扑排序
      else return new int[0];
    }

2. 2 DFS 深度优先

  • 深度优先搜索需要依赖一个节点的辅助数组默认都为0如下:(当然这里节点也作为数组下标,如果节点和下标不能一一对应,可以使用一个map哈希表去记录下节点与辅助值的映射表)
    【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS),数据结构,宽度优先,数据结构,dfs,bfs,图搜索
    标记值为0:代表搜索起点(dfs入口)
    标记值为1:代表搜索中(如果搜索中碰到值标记值为1的节点,说明有环)
    标记值为2:代表搜索完成(搜索过程无环)

  • 然后还需要准备一个节点指向集合,记录节点与节点的指向关系(后续依照这个指向将被指向的节点的值做标记)
    【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS),数据结构,宽度优先,数据结构,dfs,bfs,图搜索

  • 最后当标记值为2的时候,就代表此次dfs无环,利用一个栈将标记值为2的节点加入到栈中(栈的加入顺序就是拓扑排序的顺序)

  • 需要一个标志位(初始为true),如果搜索中dfs碰到节点值为1的节点的时候,代表出现了环,则直接将标志位标为false,结束此次递归

  List<List<Integer>> cousList;
    int[] cous;
    boolean valid = true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
    
     cous = new int[numCourses];// 构造标志位 初始化全部位0  长度为节点数

     cousList = new ArrayList<>();//给集合中节点与被指向节点初始化集合

    for(int i = 0 ;i < numCourses ; i++) //指向(父节点)与被指向(子节点)的集合映射
      cousList.add(new ArrayList<>());
 
    for(int[] pre : prerequisites){//给集合中父1节点设置指向子节点的子集合
       cousList.get(pre[1]).add(pre[0]);
    }

    for(int i = 0 ; i<numCourses ; i++){//
      if(cous[i] == 0)  dfs(i);  //等于0未搜索过 进入dfs
    }

    return valid;

  }
     
    public void dfs(int c){
        cous[c] = 1;
        for(int cur : cousList.get(c)){//遍历该父节点的子节点集合
          if(cous[cur]==0){//如果指向的节点未搜索过,则深搜
            dfs(cur);
            if(!valid){
              return;
            }
          }else if(cous[cur]==1){//如果指向节点在搜索中,则有环,标记Vaild
                valid = false;
                return;
          }

        }
    cous[c]=2;//因为节点已经完成深搜,所以标记它的状态搜索完成
  }

// 方法二  dfs 深度优先
    int[] cou = null;// 设置全局变量  方便dfs使用
    int[] num = null;
    List<List<Integer>> couList = null;
    boolean valid = true;
    Deque<Integer> queue = null;
  public int[] findOrder(int numCourses, int[][] prerequisites) {
     this.cou = new int[numCourses];// 构造标志位 初始化全部位0  长度为节点数

     this.queue = new LinkedList<>();//用于配合输出拓扑排序

     this.num  = new int[numCourses];//用于存储拓扑排序

     this.couList = new ArrayList<>();//给集合中节点与被指向节点初始化集合

    for(int i = 0 ;i<numCourses ;i++)//指向(父节点)与被指向(子节点)的集合初始化
        couList.add(new ArrayList<Integer>());
   
    for(int[] pre : prerequisites){
      couList.get(pre[1]).add(pre[0]);//指向(父节点)与被指向(子节点)的集合映射
    }

    for(int i = 0 ; i<numCourses ;i++){
        if(cou[i] == 0)  dfs(i);//等于0未搜索过 进入dfs
    }

    if(queue.size() != numCourses) return new int[0]; //如果dfs完成之后  栈内元素个数不等于节点总数  说明 拓扑排序不完整,存在环,自然不能将全部节点遍历完,
    else{//否则就代表无环  可以得到完整的拓扑排序
      for(int i = 0 ; i<numCourses ; i++){
        num[i] = queue.pop();//将压栈的节点取出来 放到数组里面
      }
    }  
      return num;
  }


  public void dfs(int i){
    cou[i] = 1;
    for(int cur : couList.get(i)){//遍历该父节点的子节点集合
      if(cou[cur] == 0){//节点标记数组对应的值等于 0  继续递归
        dfs(cur);
        if(!valid) return ;  //根据标记为判断是否有环  有环说明不能得到拓扑排序 直接返回 不往下面执行了

      }else if(cou[cur] == 1){//如果搜索中存在环  将标志位设为fasle 
         valid = false;
         return;
      }
    }
    //一次遍历结束无环  就让该遍历元素位置的节点数组数值置为  2  代表以该点进行dfs  无环
    cou[i] = 2;
    queue.push(i); //让该dfs完的节点压栈  为什么要压栈  因为最后的拓扑排序,就是栈的出栈顺序
  }

3. 有向图有环无环判定

具体怎么判定有环和无环:

BFS下

本身这两种判断方式原理是一样的,如果节点都能根据箭头遍历得到,自然得到的拓扑排序数组的长度就是节点总数,否则拓扑排序数组的长度不等于节点总数,说明有节点并没有遍历到,说明存在了环。

  1. 第一种判断方式:如果最后得到的数组(拓扑排序)的长度不等于节点总数,则代表有环,使得bfs并没有按照箭头指向走完整个图,所以出现了环
  2. 第二种判断方式:每次让队列弹出一个入度为0的节点时,让节点总数减1,如果最后节点总数 == 0,说明无环,每个元素都被bfs到了

DFS下

  1. 最后的栈里面存的就是遍历到的节点,如果最后dfs结束后的栈的大小不等于节点总数,说明有节点没有被遍历到,说明出现了环,否则如果栈的大小等于节点数,代表都遍历到了,该图无环

栈的出栈顺序就是拓扑排序的循序文章来源地址https://www.toymoban.com/news/detail-701067.html

到了这里,关于【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 用go语言实现一个构建有向图的函数,同时图结构的点和边上都支持添加属性

    当然可以。下面是一个简单的用Go语言实现的有向图构建函数的示例。这个图结构使用map来存储,每个节点都由一个唯一的标识符(id)表示,并且节点和边都可以附加属性。 go 这个示例代码创建了一个有向图,并添加了两个节点(A和B)和一个从A到B的边。每个节点和边都有

    2024年01月20日
    浏览(32)
  • 有向图的拓扑排序

    拓扑排序 。任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为尾的弧;c.重复上述a、b,直到全部顶点都已输出,此时,顶点输出序列即为一个拓朴有序序列;或者直到

    2024年02月09日
    浏览(46)
  • 有向图的强连通分量

    对于一个有向图,连通分量:对于分量中任意两点u,v,必然可以从u走到v,且从v走到u. 强连通分量:极大连通分量。 求出强连通分量后,可以通过将强连通分量缩点的方式,将有向图转化成有向无环图。 求强连通分量的方法:tarjan O(n+m),时间复杂度是线性的 1 . 采用dfs来遍历整

    2024年02月10日
    浏览(38)
  • 公开游戏、基于有向图的游戏

    目录 〇,背景 一,公开游戏、策梅洛定理 1,公开游戏 2,策梅洛定理 3,非有向图游戏的公开游戏 力扣 486. 预测赢家(区间DP) 力扣 877. 石子游戏(退化贪心) 力扣 1140. 石子游戏 II(二维DP) 力扣 1406. 石子游戏 III(数列DP) 力扣 1563. 石子游戏 V(区间DP)  力扣 1686.

    2024年02月09日
    浏览(43)
  • 有向图的强连通分量算法

    有向图的强连通分量算法 强连通分量定义 在有向图中,某个子集中的顶点可以直接或者间接互相可达,那么这个子集就是此有向图的一个强连通分量,值得注意的是,一旦某个节点划分为特定的强连通分量后,此顶点不能在其它子树中重复使用,隐含了图的遍历过程和极大

    2024年02月06日
    浏览(75)
  • 2023-04-09 有向图及相关算法

    有向图的的应用场景 社交网络中的关注 互联网连接 程序模块的引用 任务调度 学习计划 食物链 论文引用 无向图是特殊的有向图,即每条边都是双向的 改进Graph和WeightedGraph类使之支持有向图 Graph类的改动 WeightedGraph类的改动 有些问题,在有向图中不存在,或者我们通常不考

    2024年02月05日
    浏览(45)
  • 真题详解(有向图)-软件设计(六十二)

    真题详解(极限编程)-软件设计(六十一) https://blog.csdn.net/ke1ying/article/details/130435971 CMM指软件成熟度模型,一般1级成熟度最低,5级成熟度最高,采用更高级的CMM模型可以提高软件质量。 初始:杂乱无章。 可重复级:建立基本的项目管理过程和跟踪费用项。 已定义(确定)

    2024年02月01日
    浏览(60)
  • 2023-8-29 有向图的拓扑排序

    题目链接:有向图的拓扑排序

    2024年02月11日
    浏览(34)
  • 搜索与图论-有向图的拓扑序列

    有向图的拓扑序列就是图的广度优先遍历的一个应用。 若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x 在 A 中都出现在 y 之前,则称 A 是该图的一个 拓扑序列 。(起点在终点的前面) 拓扑序列是针对有向图,无向图是没有拓扑序列的。 有向无环图一定是

    2024年02月01日
    浏览(41)
  • 有向图的邻接表和邻接矩阵

    有向图的邻接表是一种常用的表示方法,用于表示图中各个节点之间的关系。在有向图中,每条边都有一个方向,因此邻接表中的每个节点记录了该节点指向的其他节点。 具体来说,有向图的邻接表由一个由节点和它们的邻居节点列表组成的集合构成。对于每个节点,邻接表

    2024年02月22日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包