有向图拓扑排序

前言

本文介绍有向图拓扑排序算法的思路及代码实现，首先讲解什么是拓扑排序，其次介绍实现拓扑排序需要的检测有向图是否有环的算法及顶点排序算法，最终实现有向图的拓扑排序。

一、什么是拓扑排序？

• 给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明
  确的表示出每个顶点的优先级。如对下图进行拓扑排序：
  
• 拓扑排序结果为：
  
• 根据拓扑排序的概念，如果对有向图进行拓扑排序，那么图中必须没有环，否则，就不能进行拓扑排序，然后在图中无环的情况下，再进行顶点排序，最终实现拓扑排序。

二、检测有向图中是否有环

• 算法思路：基于深度优先搜索算法检测图中是否有环。1. 定义boolean辅助数组onStack，以栈的思想标识顶点是否在搜索中；2. 在深度优先搜索中，不断检测当前搜索的顶点是否在栈中（即当前顶点的值是否为true，如果为true，则在栈中，否则不在栈中），如果在栈中，说明该顶点被重复搜索到，代表图中有环；3. 每个顶点深度优先搜索完成，onStack需要出栈（即将当前索引对应的值修改为false），为下个顶点搜索做准备
• 示例：
  
  
  
  
• 代码实现

public class DirectedCycle {
    private boolean[] marked;//索引代表顶点，用于标识顶点是否搜索过,是深度优先搜索的复杂数组
    private boolean hasCycle;//记录图中是否有环
    private boolean[] onStack; //索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的栈上，如果有，则证明有环。

    //创建一个检测环对象，检测图G中是否有环
    DirectedCycle(DirectGraph G)
    {
        this.marked=new boolean[G.V()];//用于标识顶点是否搜索过
        this.hasCycle=false;
        this.onStack=new boolean[G.V()];//用于标识顶点是否在搜索中

        //遍历所有顶点，将未搜索过的顶点作为入口，进行深度优先遍历，检测是否有环，一旦检测到有环，则结束；
        //因为对于不连通图，有很多个子图，也许某个子图存在环，因此，要对每个子图进行深度优先遍历检测，而不能只检测某一个子图。
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v])
                dfs(G,v);//每次搜索一个子图，判断子图内是否有环，如果没环，继续搜索下一个子图（一次搜索后，未搜索的顶点一定在另一个子图中）
        }
    }

    //基于深度优先搜索，检测图G中是否有环
    private void dfs(DirectGraph G,int v)
    {
        //1.当前顶点标记为已搜索
        marked[v]=true;
        //2.当前顶点入栈
        onStack[v]=true;
        //3.递归深度优先遍历，检查遍历结点是否已经在栈中，如果在栈中，则表明该顶点被两次搜索到，证明有环，则结束
        for (Integer w : G.adj(v)) {
            if (!marked[w])
                dfs(G,w);
            //如果该顶点已经被搜索过，且如果该顶点在搜索的路径上，则代表又一次搜索到该顶点，证明有环，结束搜索。
            if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }
        //4.当前顶点出栈，为下一个节点作为入口，检测是否有环做准备(为什么需要这样，图2.png可以解释)
        onStack[v]=false;
    }
    //判断当前有向图G中是否有环
    public boolean hasCycle()
    {
        return hasCycle;
    }
}

代码中为什么每个顶底深度优先搜索完成后onStack需要出栈，下图可以解释：

三、基于深度优先的顶点排序

• 拓扑排序使得所有的有向边均从排在前面的元素指向排在后面的元素，要实现这一需要，可以通过顶点排序进行实现。
• 顶点排序算法思路：1. 定义栈stack用于存储顶点排序的结果；2. 基于深度优先搜索算法，每个顶点深度优先搜索完成后，将该顶点入栈；3. 依次弹出栈中顶点，即为满足拓扑排序要求的顶点序列。
• 顶点排序示例：
  
  
  
  
  
  
• 代码实现

public class DepthFirstOrder {
    private boolean[] marked;//索引代表顶点，值表示当前顶点是否已经被搜索
    private Stack<Integer> reversePost;//使用栈，存储顶点序列，打印出栈中的顶点，即是排序后的顶点

    public DepthFirstOrder(DirectGraph G)
    {
        //初始化辅助变量
        this.marked=new boolean[G.V()];//默认全部赋值为false
        this.reversePost=new Stack<Integer>();
        //对每一个未搜索过的顶点进行深度优先遍历
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v])
                dfs(G,v);
        }
    }

    //基于深度优先搜索，生成顶点线性序列
    private void dfs(DirectGraph G,int v)
    {
        //1. 将当前顶点标记为已搜索
        marked[v]=true;
        //2. 遍历当前顶点的邻接表，对邻接表中未搜索的顶点递归调用深度优先搜索
        for (Integer w : G.adj(v)) {
            if(!marked[w])
                dfs(G,w);
        }
        //3. 当前顶点v深度优先搜索完毕后，入栈
        reversePost.push(v);
    }
    //获取顶点线性序列
    public Stack<Integer> reversePost()
    {
        return reversePost;
    }
}

四、拓扑排序实现

• 实现了检测是否有环和顶点排序算法，也就完成了拓扑排序，拓扑排序是对上面两个算法的封装。
• 拓扑排序算法步骤：1. 定义栈用于存储拓扑排序顶底；2. 检测图中是否有环；3. 若有环则不做拓扑排序，若无环则对图进行顶点排序，完成拓扑排序
• 代码实现

public class TopoLogical {
    private Stack<Integer> order; //顶点的拓扑排序

    public TopoLogical(DirectGraph G)
    {
        //1. 检测是否有环
        DirectedCycle directedCycle = new DirectedCycle(G);
        if (!directedCycle.hasCycle())
        {
            //2. 调用顶点排序算法
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
            this.order=depthFirstOrder.reversePost();
        }
    }

    //判断图G是否有环
    public boolean isCycle()
    {
        return order==null;
    }
    //获取拓扑排序的所有顶点
    public Stack<Integer> order()
    {
        return order;
    }
}