【数据结构与算法】有向图的拓扑排序

朱雀 2023-09-23 13:47 130阅读 0赞

### 前言 ###

在现实生活中，我们经常会同一时间接到很多任务去完成，但是这些任务的完成是有先后次序的。以我们学习java

学科为例，我们需要学习很多知识，但是这些知识在学习的过程中是需要按照先后次序来完成的。从java基础，到

jsp/servlet，到ssm，到springboot等是个循序渐进且有依赖的过程。在学习jsp前要首先掌握java基础和html基

础，学习ssm框架前要掌握jsp/servlet之类才行。

![format_png][]

为了简化问题，我们使用整数为顶点编号的标准模型来表示这个案例：

![format_png 1][]

此时如果某个同学要学习这些课程，就需要指定出一个学习的方案，我们只需要对图中的顶点进行排序，让它转换为一个线性序列，就可以解决问题，这时就需要用到一种叫**拓扑排序**的算法。

### 拓扑排序介绍 ###

给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明确的表示出每个顶点的优先级。下列是一副拓扑排序后的示意图:

![format_png 2][]

### 检测有向图中的环 ###

如果学习x课程前必须先学习y课程，学习y课程前必须先学习z课程，学习z课程前必须先学习x课程，那么一定是有问题了，我们就没有办法学习了，因为这三个条件没有办法同时满足。其实这三门课程x、y、z的条件组成了一个环：

![format_png 3][]

因此，如果我们要使用拓扑排序解决优先级问题，首先得保证图中没有环的存在。

#### 实现思路 ####

在API中添加了onStack\[\] 布尔数组，索引为图的顶点，当我们深度搜索时：

1.  在如果当前顶点正在搜索，则把对应的onStack数组中的值改为true，标识进栈；
2.  如果当前顶点搜索完毕，则把对应的onStack数组中的值改为false，标识出栈；
3.  如果即将要搜索某个顶点，但该顶点已经在栈中，则图中有环；

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

#### API设计 ####

<table> 
 <thead> 
  <tr> 
   <th><strong>类名</strong></th> 
   <th><strong>DirectedCycle</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>成员变量</td> 
   <td>1.private boolean[] marked: 索引代表顶点，值表示当前顶点是否已经被搜索2.private boolean hasCycle: 记录图中是否有环3.private boolean[] onStack:索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上</td> 
  </tr> 
  <tr> 
   <td>构造方法</td> 
   <td>DirectedCycle(Digraph G)：创建一个检测环对象，检测图G中是否有环</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td>1.private void dfs(Digraph G,int v)：基于深度优先搜索，检测图G中是否有环2.public boolean hasCycle():判断图中是否有环</td> 
  </tr> 
 </tbody> 
</table>

#### 代码实现 ####

/**
     * 有向图是否存在环
     *
     * @author alvin
     * @date 2022/11/2
     * @since 1.0
     **/
    public class DirectedCycle {
        //索引代表顶点，值表示当前顶点是否已经被搜索
        private boolean[] marked;
        //记录图中是否有环
        private boolean hasCycle;
        //索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
        private boolean[] onStack;
    
        //创建一个检测环对象，检测图G中是否有环
        public DirectedCycle(Digraph G){
            //初始化marked数组
            this.marked = new boolean[G.V()];
            //初始化hasCycle
            this.hasCycle = false;
            //初始化onStack数组
            this.onStack = new boolean[G.V()];
    
            //找到图中每一个顶点，让每一个顶点作为入口，调用一次dfs进行搜索
            for (int v =0; v<G.V();v++){
                //判断如果当前顶点还没有搜索过，则调用dfs进行搜索
                if (!marked[v]){
                    dfs(G,v);
                }
            }
        }
    
        //基于深度优先搜索，检测图G中是否有环
        private void dfs(Digraph G, int v){
            //把顶点v表示为已搜索
            marked[v] = true;
            //把当前顶点进栈
            onStack[v] = true;
    
            for(Integer w: G.adj(v)) {
                //判断如果当前顶点w没有被搜索过，则继续递归调用dfs方法完成深度优先搜索
                if(!marked[w]) {
                    dfs(G, w);
                }
    
                //判断当前顶点w是否已经在栈中，如果已经在栈中，证明当前顶点之前处于正在搜索的状态，那么现在又要搜索一次，证明检测到环了
                if (onStack[w]){
                    hasCycle = true;
                    return;
                }
            }
            //把当前顶点出栈
            onStack[v] = false;
        }
    
        //判断当前有向图G中是否有环
        public boolean hasCycle(){
            return hasCycle;
        }
    }
    复制代码

### 基于深度优先的顶点排序 ###

#### 实现思路 ####

如果要把图中的顶点生成线性序列其实是一件非常简单的事，之前我们学习并使用了多次深度优先搜索，我们会发现其实深度优先搜索有一个特点，那就是在一个连通子图上，每个顶点只会被搜索一次，如果我们能在深度优先搜索的基础上，添加一行代码，只需要将搜索的顶点放入到线性序列的数据结构中，我们就能完成这件事。

我们添加了一个栈reversePost用来存储顶点，当我们深度搜索图时，每搜索完毕一个顶点，把该顶点放入到reversePost中，这样就可以实现顶点排序。

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

![format_png 13][]

![format_png 14][]

![format_png 15][]

![format_png 16][]

#### API设计 ####

<table> 
 <thead> 
  <tr> 
   <th><strong>类名</strong></th> 
   <th><strong>DepthFirstOrder</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>成员变量</td> 
   <td>1.private boolean[] marked: 索引代表顶点，值表示当前顶点是否已经被搜索2.private Stack reversePost: 使用栈，存储顶点序列</td> 
  </tr> 
  <tr> 
   <td>构造方法</td> 
   <td>DepthFirstOrder(Digraph G)：创建一个顶点排序对象，生成顶点线性序列；</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td>1.private void dfs(Digraph G,int v)：基于深度优先搜索，生成顶点线性序列2.public Stack reversePost():获取顶点线性序列</td> 
  </tr> 
 </tbody> 
</table>

#### 代码实现 ####

/**
     * 顶点排序
     *
     * @author alvin
     * @date 2022/11/2
     * @since 1.0
     **/
    public class DepthFirstOrder {
        //索引代表顶点，值表示当前顶点是否已经被搜索
        private boolean[] marked;
        //使用栈，存储顶点序列
        private Stack<Integer> reversePost;
    
        //创建一个检测环对象，检测图G中是否有环
        public DepthFirstOrder(Digraph G){
            //初始化marked数组
            this.marked = new boolean[G.V()];
            //初始化reversePost栈
            this.reversePost = new Stack<>();
    
            //遍历图中的每一个顶点，让每个顶点作为入口，完成一次深度优先搜索
            for (int v = 0;v<G.V();v++){
                if (!marked[v]){
                    dfs(G,v);
                }
            }
        }
    
        //基于深度优先搜索，把顶点排序
        private void dfs(Digraph G, int v){
            //标记当前v已经被搜索
            marked[v] = true;
            //通过循环深度搜索顶点v
            for (Integer w : G.adj(v)) {
                //如果当前顶点w没有搜索，则递归调用dfs进行搜索
                if (!marked[w]){
                    dfs(G,w);
                }
            }
            //让顶点v进栈
            reversePost.push(v);
        }
    
        //获取顶点线性序列
        public Stack<Integer>  reversePost(){
            return reversePost;
        }
    }
    复制代码

### 拓扑排序 ###

前面已经实现了环的检测以及顶点排序，那么拓扑排序就很简单了，基于一幅图，先检测有没有环，如果没有环，则调用顶点排序即可。

#### API设计 ####

<table> 
 <thead> 
  <tr> 
   <th><strong>类名</strong></th> 
   <th><strong>TopoLogical</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>成员变量</td> 
   <td>1.private Stack order: 顶点的拓扑排序</td> 
  </tr> 
  <tr> 
   <td>构造方法</td> 
   <td>TopoLogical(Digraph G)：构造拓扑排序对象</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td>1.public boolean isCycle()：判断图G是否有环2.public Stack order():获取拓扑排序的所有顶点</td> 
  </tr> 
 </tbody> 
</table>

#### 代码实现 ####

/**
     * 拓扑排序
     *
     * @author alvin
     * @date 2022/11/2
     * @since 1.0
     **/
    public class TopoLogical {
        //顶点的拓扑排序
        private Stack<Integer> order;
    
        //构造拓扑排序对象
        public TopoLogical(Digraph G) {
            //创建一个检测有向环的对象
            DirectedCycle cycle = new DirectedCycle(G);
            //判断G图中有没有环，如果没有环，则进行顶点排序：创建一个顶点排序对象
            if (!cycle.hasCycle()){
                DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
                order = depthFirstOrder.reversePost();
            }
        }
    
        //判断图G是否有环
        private boolean isCycle(){
            return order==null;
        }
    
        //获取拓扑排序的所有顶点
        public Stack<Integer> order(){
            return order;
        }
    }
    复制代码

#### 测试验证 ####

public class TopoLogicalTest {
    
        @Test
        public void test() {
            //准备有向图
            Digraph digraph = new Digraph(6);
            digraph.addEdge(0,2);
            digraph.addEdge(0,3);
            digraph.addEdge(2,4);
            digraph.addEdge(3,4);
            digraph.addEdge(4,5);
            digraph.addEdge(1,3);
    
            //通过TopoLogical对象堆有向图中的顶点进行排序
            TopoLogical topoLogical = new TopoLogical(digraph);
    
            //获取顶点的线性序列进行打印
            Stack<Integer> order = topoLogical.order();
            StringBuilder sb = new StringBuilder();
            while (order.size() != 0) {
                sb.append(order.pop()+"->");
            };
            String str = sb.toString();
            int index = str.lastIndexOf("->");
            str = str.substring(0,index);
            System.out.println(str);
        }
    }
    复制代码

![format_png 17][]

[format_png]: https://img-blog.csdnimg.cn/img_convert/1a790bda175df988acedaf1e3d51bff9.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/1cd67cfe83c69c658710a6fd210a5124.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/3ea126ab02e1959d7e360d4236b3d618.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/e8df2833354ccf0b4aa93553589ca44f.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/b036f45c87e3f768506a6225b8d0bb8a.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/fc211128afae03cf455ab5860564ed22.webp?x-oss-process=image/format,png
[format_png 6]: https://img-blog.csdnimg.cn/img_convert/635c59cc23c9615d5724bc8d550b3e6f.webp?x-oss-process=image/format,png
[format_png 7]: https://img-blog.csdnimg.cn/img_convert/cd4d302010f137ed62c25cd76b544c8d.webp?x-oss-process=image/format,png
[format_png 8]: https://img-blog.csdnimg.cn/img_convert/93e3795693cc40d01b2045f9af6670ac.webp?x-oss-process=image/format,png
[format_png 9]: https://img-blog.csdnimg.cn/img_convert/eb00a6f93a5e943043818267045b8d77.webp?x-oss-process=image/format,png
[format_png 10]: https://img-blog.csdnimg.cn/img_convert/4ec0eb6f59f4d8c806c44ce58be11d2d.webp?x-oss-process=image/format,png
[format_png 11]: https://img-blog.csdnimg.cn/img_convert/53a4d109b56e084ca7e9d93163f08a68.webp?x-oss-process=image/format,png
[format_png 12]: https://img-blog.csdnimg.cn/img_convert/5d24b95e3aed31b9ce482bf02d9fbb37.webp?x-oss-process=image/format,png
[format_png 13]: https://img-blog.csdnimg.cn/img_convert/ad44799bb9b6a0d5116b0f02a70c74c6.webp?x-oss-process=image/format,png
[format_png 14]: https://img-blog.csdnimg.cn/img_convert/aef6938b27311f9937df7e25c396bbfc.webp?x-oss-process=image/format,png
[format_png 15]: https://img-blog.csdnimg.cn/img_convert/09256aa2d817f83821778108bfc70279.webp?x-oss-process=image/format,png
[format_png 16]: https://img-blog.csdnimg.cn/img_convert/9e404b0c9a2c40bd43ffd881c5763c8e.webp?x-oss-process=image/format,png
[format_png 17]: https://img-blog.csdnimg.cn/img_convert/8dee08571cdf76f66f450a7bbe0a11a5.webp?x-oss-process=image/format,png