登录  /  注册
首页 > Java > java教程 > 正文

Java如何实现拓扑排序

WBOY
发布: 2023-06-01 12:20:02
转载
1058人浏览过

    铺垫

    我们本节将介绍与有向图相关的算法,因此先对有向图的一些概念进行解释;之后的文章将不再对这些概念做具体解释。首先有向图节点与节点之间是用带箭头的线连接起来的。节点的出度和入度可用来描述,当一条连线的尾部指向该节点时,其出度会增加1;而当一条连线的箭头指向该节点时,其入度会增加1。看下面这个例子,a的入度为0,出度为2,b的入度为1,出度为1,c的入度为1,出度为1,d的入度为2,出度为0。

    Java如何实现拓扑排序

    邻接表:邻接表是存储图结构的一种有效方式,如下图所示,左边节点数组存储图中所有节点,右侧邻接表存储节点的相邻节点。

    Java如何实现拓扑排序

    简介

    这篇文章我们要讲的是拓扑排序,这是一个针对有向无环图的算法,主要是为了解决前驱后继的关系,即我们在完成当前事项的时候需要先完成什么事项,其实这在我们流程控制里面用的挺多的。看下面这个图,我们需要先完成A事项,然后才能去完成B,C事项,B,C事项的属于并列的,没有先后顺序,但是对于D事项需要在B,C事项完成之后才能进行。而拓扑排序能够帮助我们找到这个完成事项的合理顺序,同时我们看上面这个例子,A事项完成之后,B,C事项是没有先后顺序的,不管是先完成B还是C都符合条件,所以拓扑排序的顺序序列不是完全一定的。

    工作过程

    首先拓扑排序对应操作的是一个有向无环图。无环图,则肯定存在至少一个结点入度为0。在当前情况下,我们需要查找入度为0的节点进行操作,入度为0,表示当前节点没有前驱节点,或者前驱节点已经处理,可以直接操作。操作完毕之后,将当前节点的后继节点入度全部减1,再次查找入度节点为0的节点进行操作,此后就是一个递归过程,不断处理当前情况下入度为0的节点,直至所有节点处理完毕。

    Java如何实现拓扑排序

    数据结构

    以下是有向图的结构,其中node存储着当前图中的所有节点,adj则存储着对应下标节点的邻接点。在初始化图时,需指定节点数量、建立节点数组和邻接数组。提供一个名为addEdge的方法,用于将两个节点之间建立一条边,即将后继节点添加到前驱节点的邻接表中。

    public static class Graph{
           /**
            * 节点个数
            */
           private Integer nodeSize;
           /**
            * 节点
            */
           private char[] node;
           /**
            * 邻接表
            */
           private LinkedList[] adj;
    
           public Graph(char[] node) {
               this.nodeSize = node.length;
               this.node = node;
               this.adj = new LinkedList[nodeSize];
               for (int i = 0 ; i < adj.length ; i++) {
                   adj[i] = new LinkedList();
              }
          }
           /**
            * 在节点之间加边,前驱节点指向后继节点
            * @param front 前驱节点所在下标
            * @param end 后继节点所在下标
            */
           public void addEdge(int front, int end) {
               adj[front].add(end);
          }
      }
    登录后复制

    拓扑排序

    拓扑排序首先初始化了两个临时数组,一个队列,一个inDegree数组存储对应下标节点的入度,因为每次访问的节点需要前驱节点已经完成,即入度为0,有了这个数组我们就可以比较快速的找到这些节点;另一个是visited数组,标志当前节点是否已经访问过,防止多次访问;一个nodes队列则保存在目前情况下所有入度为0的节点。(注意,为了存取方便,我们都是存储的节点下标 step1:初始化inDegree数组,visited数组; step2:遍历inDegree数组,将所有入度为0的节点入nodes队列; step3:依次将节点node出队; 根据visited判断当前node是否已经被访问,是,返回step3,否,进行下一步; 将当前节点的邻接节点入度-1,判断邻接节点入度是否为0,为0直接放入nodes队列,不为0返回step3;

    /**
        * @param graph 有向无环图
        * @return 拓扑排序结果
        */
       public List<Character> toPoLogicalSort(Graph graph) {
           //用一个数组标志所有节点入度
           int[] inDegree = new int[graph.nodeSize];
           for (LinkedList list : graph.adj) {
               for (Object index : list) {
                   ++ inDegree[(int)index];
              }
          }
           //用一个数组标志所有节点是否已经被访问
           boolean[] visited = new boolean[graph.nodeSize];
           //开始进行遍历
           Deque<Integer> nodes = new LinkedList<>();
           //将入度为0节点入队
           for (int i = 0 ; i < graph.nodeSize; i++) {
               if (inDegree[i] == 0) {
                   nodes.offer(i);
              }
          }
           List<Character> result = new ArrayList<>();
           //将入度为0节点一次出队处理
           while (!nodes.isEmpty()) {
               int node = nodes.poll();
               if (visited[node]) {
                   continue;
              }
               visited[node] = true;
               result.add(graph.node[node]);
               //将当前node的邻接节点入度-1;
               for (Object list : graph.adj[node]) {
                   -- inDegree[(int)list];
                   if (inDegree[(int)list] == 0) {
                       //前驱节点全部访问完毕,入度为0
                       nodes.offer((int) list);
                  }
              }
          }
           return result;
      }
    登录后复制

    测试样例1

    public static void main(String[] args) {
           ToPoLogicalSort toPoLogicalSort = new ToPoLogicalSort();
           //初始化一个图
           Graph graph = new Graph(new char[]{&#39;A&#39;, &#39;B&#39;, &#39;C&#39;, &#39;D&#39;});
           graph.addEdge(0, 1);
           graph.addEdge(0,2);
           graph.addEdge(1,3);
           graph.addEdge(2,3);
           List<Character> result = toPoLogicalSort.toPoLogicalSort(graph);
      }
    登录后复制

    执行结果

    Java如何实现拓扑排序

    测试样例2

    public static void main(String[] args) {
           ToPoLogicalSort toPoLogicalSort = new ToPoLogicalSort();
           //初始化一个图
           Graph graph = new Graph(new char[]{&#39;A&#39;, &#39;B&#39;, &#39;C&#39;, &#39;D&#39;,&#39;E&#39;,&#39;F&#39;,&#39;G&#39;,&#39;H&#39;});
           graph.addEdge(0, 1);
           graph.addEdge(0,2);
           graph.addEdge(0,3);
           graph.addEdge(1,4);
           graph.addEdge(2,4);
           graph.addEdge(3,4);
           graph.addEdge(4,7);
           graph.addEdge(4,6);
           graph.addEdge(7,5);
           graph.addEdge(6,7);
           List<Character> result = toPoLogicalSort.toPoLogicalSort(graph);
      }
    登录后复制

    执行结果

    Java如何实现拓扑排序

    以上就是Java如何实现拓扑排序的详细内容,更多请关注php中文网其它相关文章!

    智能AI问答
    PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
    来源:亿速云网
    本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
    最新问题
    热门教程
    更多>
    最新下载
    更多>
    网站特效
    网站源码
    网站素材
    前端模板
    关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
    php中文网:公益在线php培训,帮助PHP学习者快速成长!
    关注服务号 技术交流群
    PHP中文网订阅号
    每天精选资源文章推送
    PHP中文网APP
    随时随地碎片化学习
    PHP中文网抖音号
    发现有趣的

    Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号