《算法》第四章部分程序 part 9

▶ 书中第四章部分程序，包括在加上自己补充的代码，两种拓扑排序的方法

● 拓扑排序 1

 package package01;

 import edu.princeton.cs.algs4.Digraph;

 import edu.princeton.cs.algs4.SymbolDigraph;

 import edu.princeton.cs.algs4.DirectedCycle;

 import edu.princeton.cs.algs4.DepthFirstOrder;

 import edu.princeton.cs.algs4.EdgeWeightedDigraph;

 import edu.princeton.cs.algs4.EdgeWeightedDirectedCycle;

 public class class01

 {

     private Iterable<Integer> order;    // 拓扑排序的结果

     private int[] rank;                 // 顶点 v 在拓扑排序中的序号为 rank[v]

     public class01(Digraph G)           // 从有向图生成拓扑排序

     {

         DirectedCycle finder = new DirectedCycle(G);        // 存在环则不能排序

         if (!finder.hasCycle())

         {

             DepthFirstOrder dfs = new DepthFirstOrder(G);   // 做 G 的深度优先搜索

             order = dfs.reversePost();                      // 取逆后序依次标号

             rank = new int[G.V()];

             int i = 0;

             for (int v : order)

                 rank[v] = i++;

         }

     }

     public class01(EdgeWeightedDigraph G)                   // 从加权边有向图生成拓扑排序（算法一样，只是数据结构不同）

     {

         EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);

         if (!finder.hasCycle())

         {

             DepthFirstOrder dfs = new DepthFirstOrder(G);

             order = dfs.reversePost();

             rank = new int[G.V()];

             int i = 0;

             for (int v : order)

                 rank[v] = i++;

         }

     }

     public Iterable<Integer> order()

     {

         return order;

     }

     public boolean hasOrder()

     {

         return order != null;

     }

     public int rank(int v)

     {

         return hasOrder() ? rank[v] : -1;

     }

     public static void main(String[] args)

     {

         String filename = args[0];

         String delimiter = args[1];                                 // 分隔符

         SymbolDigraph sg = new SymbolDigraph(filename, delimiter);

         class01 topological = new class01(sg.digraph());

         for (int v : topological.order())

             System.out.println(sg.nameOf(v));

     }

 }

● 拓扑排序 2

 package package01;

 import edu.princeton.cs.algs4.StdOut;

 import edu.princeton.cs.algs4.StdRandom;

 import edu.princeton.cs.algs4.DigraphGenerator;

 import edu.princeton.cs.algs4.Digraph;

 import edu.princeton.cs.algs4.Queue;

 import edu.princeton.cs.algs4.DirectedEdge;

 import edu.princeton.cs.algs4.EdgeWeightedDigraph;

 public class class01

 {

     private Queue<Integer> order;

     private int[] rank;

     public class01(Digraph G)

     {

         order = new Queue<Integer>();

         rank = new int[G.V()];

         int[] indegree = new int[G.V()];

         for (int v = 0; v < G.V(); v++)

             indegree[v] = G.indegree(v);

         int count = 0;

         Queue<Integer> queue = new Queue<Integer>();

         for (int v = 0; v < G.V(); v++)                 // 收集所有没有前提条件的顶点

         {

             if (indegree[v] == 0)

                 queue.enqueue(v);

         }

         for (; !queue.isEmpty();)

         {

             int v = queue.dequeue();

             order.enqueue(v);                           // 事件 v 完成，将其放入输出队列， 并给一个序号

             rank[v] = count++;

             for (int w : G.adj(v))                      // 所有紧接着 v 的事件的前提条件减少 1

             {

                 indegree[w]--;

                 if (indegree[w] == 0)                   // 收集此时没有前提条件的事件

                     queue.enqueue(w);

             }

         }

         if (count != G.V())                             // 遍历结束，还有顶点有入度，说明存在环

             order = null;

     }

     public class01(EdgeWeightedDigraph G)

     {

         order = new Queue<Integer>();

         rank = new int[G.V()];

         int[] indegree = new int[G.V()];

         for (int v = 0; v < G.V(); v++)

             indegree[v] = G.indegree(v);

         int count = 0;

         Queue<Integer> queue = new Queue<Integer>();

         for (int v = 0; v < G.V(); v++)

         {

             if (indegree[v] == 0)

                 queue.enqueue(v);

         }

         for (; !queue.isEmpty();)

         {

             int v = queue.dequeue();

             order.enqueue(v);

             rank[v] = count++;

             for (DirectedEdge e : G.adj(v))

             {

                 int w = e.to();

                 indegree[w]--;

                 if (indegree[w] == 0)

                     queue.enqueue(w);

             }

         }

         if (count != G.V())

             order = null;

     }

     public Iterable<Integer> order()

     {

         return order;

     }

     public boolean hasOrder()

     {

         return order != null;

     }

     public int rank(int v)

     {

         return hasOrder() ? rank[v] : -1;

     }

     public static void main(String[] args)

     {

         int V = Integer.parseInt(args[0]);                  // 生成DAG G(V,E)，再添加 F 条边

         int E = Integer.parseInt(args[1]);

         int F = Integer.parseInt(args[2]);

         Digraph G1 = DigraphGenerator.dag(V, E);            // G1 是无边圈的

         EdgeWeightedDigraph G2 = new EdgeWeightedDigraph(V);// G2 有边权的

         for (int v = 0; v < G1.V(); v++)

         {

             for (int w : G1.adj(v))

                 G2.addEdge(new DirectedEdge(v, w, 0.0));

         }

         for (int i = 0; i < F; i++)

         {

             int v = StdRandom.uniform(V);

             int w = StdRandom.uniform(V);

             G1.addEdge(v, w);

             G2.addEdge(new DirectedEdge(v, w, 0.0));

         }

         StdOut.println(G1);

         StdOut.println();

         StdOut.println(G2);

         class01 topological1 = new class01(G1);             // 分别计算 G1 和 G2 的

         if (!topological1.hasOrder())

             StdOut.println("Not a DAG");

         else

         {

             StdOut.print("Topological order: ");

             for (int v : topological1.order())

                 StdOut.print(v + " ");

             StdOut.println();

         }

         class01 topological2 = new class01(G2);

         if (!topological2.hasOrder())

             StdOut.println("Not a DAG");

         else

         {

             StdOut.print("Topological order: ");

             for (int v : topological2.order())

                 StdOut.print(v + " ");

             StdOut.println();

         }

     }

 }