有向无环图-白红宇

有向无环图

阅读量：4214 次

发布时间：2019-05-26

本文共 8079 字，大约阅读时间需要 26 分钟。

更新：
拓扑排序有2中方法（最后结果可能不同，因为拓扑排序有多解）。
一个简单的求拓扑排序的是先找出任意一个没有入边的顶点，然后将它和它的边从图中删除。然后对剩余部分使用同样的操作。

    public ArrayList
     
     topo()    {        ArrayList
     
       result = 
      new ArrayList<>();        Queue
      
        que = 
       new LinkedList<>();        
       int[] ind = 
       new 
       int[V];        
       for(
       int i=
       0;i
       
        0;        
        for(LinkedList
        
          nodes:adj) 
         for(
         int x:nodes) ind[x]++; 
         for(
         int i=
         0;i
         
          if(ind[i]==
          0) que.offer(i); 
          while(!que.isEmpty()) { 
          int k = que.poll(); result.add(k); 
          for(
          int x:adj(k)) { ind[x]--; 
          if(ind[x]==
          0) que.offer(x); } } 
          return result; }
         
        
       
      
     
    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
   
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28

定义：拓扑排序是对有向无环图(DAG)的顶点的一种排序，使得如果存在一条从v到w的路径，那么在排序中w就出现在v的后面。
如果图含有环，那么拓扑排序是不可能的。试想有3个正整数，a比b大，b比c大，c比a大，我们无法对abc排序。

算法：
1. 一个简单的求拓扑排序的算法是先找出任意一个没有入边的顶点，然后将它和它的边从图中删除。然后对剩余部分使用同样的操作。
2. 另一种不那么直观，却更加简单的算法是求所有顶点的逆后序排列。

第二种方法：

所以我们要做的就是：
先判断该图是不是一幅有向无环图，如果是，则进行拓扑排序。在这个过程中，我们需要用dfs遍历该图2遍。

性能分析：
使用深度优先搜索对有向无环图进行拓扑排序所需的时间和V+E成正比。

检测有向图中是否有环：

用深度优先搜索来解决这个问题并不困难，一旦我们找到了一条有向边v->w且w已经存在于栈中，就找到了一个环。

实现中使用了一个onStack[]数组，以标记递归调用的栈上的所有顶点。而路径信息依然可以通过from[]数组得到。

下例是个简单实现，只能保存遍历过程中检测到的最后一条环路。但已经足够了，代码修改起来也十分简单。

package DiGraphs;import java.util.Stack;public class CycleDetect {    private DiGraph g;//有向图    private boolean[] marked;//是否被访问过    private Stack
    
      cycle;
     //存放有向环路径的栈    
     private 
     boolean[] onStack;
     //判断索引位置的顶点是否在栈中    
     private 
     int from[];
     //保存路径信息    
     public 
     CycleDetect(DiGraph g) {        
     this.g = g;        marked = 
     new 
     boolean[g.V()];        onStack = 
     new 
     boolean[g.V()];        from = 
     new 
     int[g.V()];    }    
     /**     * 遍历有向图，对所有连同分量都进行深度优先搜索     */    
     public 
     void 
     dfs(){        
     for (
     int v = 
     0; v < g.V(); v++)            
     if (!marked(v))                dfs(g, v);    }    
     /**     * 深度优先搜索，将路径信息保存在from数组。如果发现有环，则将路径放入cycle栈中。     * @param g     * @param s     */    
     private 
     void 
     dfs(DiGraph g, 
     int s) {        marked[s] = 
     true;        onStack[s] = 
     true;        
     for (
     int w : g.adj(s))            
     if (
     this.hasCycle())                
     return;            
     else 
     if (!marked(w)) {                from[w] = s;                dfs(g, w);            } 
     else 
     if (onStack[w]) {
     //如果已被访问且在栈内                cycle = 
     new Stack
     
      ();                
      for (
      int x = s; x != w; x = from[x])                    cycle.push(x);
      //将路径逆序push进栈中                cycle.push(w);                cycle.push(s);            }        onStack[s] = 
      false;    }    
      public 
      boolean 
      hasCycle() {        
      return cycle != 
      null;    }    
      public Iterable
       
       cycle(){        
       return cycle;    }    
       private 
       boolean 
       marked(
       int w) {        
       return marked[w];    }    
       public 
       static 
       void 
       main(String[] args) {        DiGraph g = 
       new DiGraph(
       13);        g.addEdge(
       0, 
       5);        g.addEdge(
       5, 
       4);        g.addEdge(
       4, 
       3);        g.addEdge(
       3, 
       5);        g.addEdge(
       5, 
       0);        CycleDetect detectCycle = 
       new CycleDetect(g);        detectCycle.dfs();        Stack
       
         st = (Stack
        
         ) detectCycle.cycle(); 
         while(!st.isEmpty()){ System.out.print(st.pop() + 
         " "); } } 
         //result: 3 5 4 3 }
        
       
      
     
    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
   
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86

基于DFS的顶点排序

人们一般对3种排序感兴趣：
前序：在递归调用之前将顶点加入队列。前序就是dfs()的调用顺序。
后序：在递归调用之后将顶点加入队列。后序就是顶点遍历完成的顺序。
逆后序：在递归调用之后将顶点压入栈。逆后序就是后序的逆序。

它们的实现都非常简单，在原本的dfs()方法中添加3行代码就能实现：

    public void dfs(DiGraph g, int v) {        pre.enQueue(v);//pre是MyQueue类型的        marked[s] = true;        for(int w:g.adj(v)){            if(!marked(w))                dfs(g,w);        }        post.enQueue(v);        reversePost.push(v);//MyArrayStack类型    }    public Iterable
     
     pre(){        
     return pre;    }    
     public Iterable
      
      post(){        
      return post;    }    
      public Iterable
       
       reversePost(){        
       return reversePost;    }
      
     
    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
   
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

拓扑排序

拓扑排序测试

package DiGraphs;import java.util.Stack;public class Topological {    private DiGraph g;    private Iterable
    
      order;
     // 拓扑排序序列    
     public 
     Topological(DiGraph g) {        
     this.g = g;    }    
     /**     * 返回拓扑排序序列，如果不存在，返回null     *      * @return     */    
     public Iterable
      
      order() {        CycleDetect cd = 
      new CycleDetect(g);        
      if (!cd.hasCycle()) {
      // 如果没有环，就排序            DiDFSOrder dfsOrder = 
      new DiDFSOrder(g);            dfsOrder.dfs();            order = dfsOrder.reversePost();
      // dfs的逆后序        }        
      return order;    }    
      public 
      static 
      void 
      main(String[] args) {        DiGraph g = 
      new DiGraph(
      8);        g.addEdge(
      0, 
      5);        g.addEdge(
      0, 
      2);        g.addEdge(
      0, 
      4);        g.addEdge(
      5, 
      4);        g.addEdge(
      5, 
      6);        g.addEdge(
      2, 
      3);        g.addEdge(
      3, 
      5);        g.addEdge(
      4, 
      7);        g.addEdge(
      6, 
      1);        Topological t = 
      new Topological(g);        Stack
      
        s = 
       new Stack
       
        ();        s = (Stack
        
         ) t.order(); 
         while (!s.isEmpty()) System.out.print(s.pop() + 
         " "); 
         //result: 0 2 3 5 6 1 4 7 正确 }}
        
       
      
     
    
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
   
   
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49

总结

拓扑排序并不是一个困难的算法，在后面的加权有向图的最短路径问题中还会遇到它。

你可能感兴趣的文章