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

▶ 书中第四章部分程序，包括在加上自己补充的代码，图的前序、后序和逆后续遍历，以及传递闭包

● 图的前序、后序和逆后续遍历

 package package01;

 import edu.princeton.cs.algs4.In;

 import edu.princeton.cs.algs4.StdOut;

 import edu.princeton.cs.algs4.Digraph;

 import edu.princeton.cs.algs4.EdgeWeightedDigraph;

 import edu.princeton.cs.algs4.DirectedEdge;

 import edu.princeton.cs.algs4.Queue;

 import edu.princeton.cs.algs4.Stack;

 public class class01

 {

     private boolean[] marked;

     private int[] pre;                  // 前序顶点列表（索引 -> 顶点）

     private int[] post;                 // 后序顶点列表

     private Queue<Integer> preorder;    // 前序队列（顶点）

     private Queue<Integer> postorder;   // 后续队列

     private int preCounter;             // 前序计数器

     private int postCounter;            // 后序计数器

     public class01(Digraph G)

     {

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

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

         postorder = new Queue<Integer>();

         preorder = new Queue<Integer>();

         marked = new boolean[G.V()];

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

         {

             if (!marked[v])

                 dfs(G, v);

         }

     }

     public class01(EdgeWeightedDigraph G)

     {

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

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

         postorder = new Queue<Integer>();

         preorder = new Queue<Integer>();

         marked = new boolean[G.V()];

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

         {

             if (!marked[v])

                 dfs(G, v);

         }

     }

     private void dfs(Digraph G, int v)

     {

         marked[v] = true;

         pre[v] = preCounter++;          // 前序和后序差别在于，将当前顶点加入队列以及递归的先后顺序

         preorder.enqueue(v);

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

         {

             if (!marked[w])

                 dfs(G, w);

         }

         postorder.enqueue(v);

         post[v] = postCounter++;

     }

     private void dfs(EdgeWeightedDigraph G, int v)

     {

         marked[v] = true;

         pre[v] = preCounter++;

         preorder.enqueue(v);

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

         {

             int w = e.to();

             if (!marked[w])

                 dfs(G, w);

         }

         postorder.enqueue(v);

         post[v] = postCounter++;

     }

     public int pre(int v)

     {

         return pre[v];

     }

     public int post(int v)

     {

         return post[v];

     }

     public Iterable<Integer> pre()

     {

         return preorder;

     }

     public Iterable<Integer> post()

     {

         return postorder;

     }

     public Iterable<Integer> reversePost()  // 用后续队列生成逆后序栈

     {

         Stack<Integer> reverse = new Stack<Integer>();

         for (int v : postorder)

             reverse.push(v);

         return reverse;

     }

     public static void main(String[] args)

     {

         In in = new In(args[0]);

         Digraph G = new Digraph(in);

         class01 dfs = new class01(G);

         StdOut.println("   v  pre post");

         StdOut.println("--------------");

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

             StdOut.printf("%4d %4d %4d\n", v, dfs.pre(v), dfs.post(v));

         StdOut.print("Preorder:  ");        // 分别输出前序、后序和逆后序

         for (int v : dfs.pre())

             StdOut.print(v + " ");

         StdOut.println();

         StdOut.print("Postorder: ");

         for (int v : dfs.post())

             StdOut.print(v + " ");

         StdOut.println();

         StdOut.print("Reverse postorder: ");

         for (int v : dfs.reversePost())

             StdOut.print(v + " ");

         StdOut.println();

     }

 }

● 传递闭包

 package package01;

 import edu.princeton.cs.algs4.In;

 import edu.princeton.cs.algs4.StdOut;

 import edu.princeton.cs.algs4.Digraph;

 import edu.princeton.cs.algs4.DirectedDFS;

 public class class01

 {

     private DirectedDFS[] tc;

     public class01(Digraph G)

     {

         tc = new DirectedDFS[G.V()];

         for (int v = 0; v < G.V(); v++)     // 循环尝试从所有点开始深度优先遍历整个图，返回可达点的迭代器

             tc[v] = new DirectedDFS(G, v);

     }

     public boolean reachable(int v, int w)

     {

         return tc[v].marked(w);

     }

     public static void main(String[] args)

     {

         In in = new In(args[0]);

         Digraph G = new Digraph(in);

         class01 tc = new class01(G);

         StdOut.print("     ");

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

             StdOut.printf("%3d", v);

         StdOut.println("\n--------------------------------------------");

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

         {

             StdOut.printf("%3d: ", v);

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

                 StdOut.printf(tc.reachable(v, w) ? "  T" : "   ");

             StdOut.println();

         }

     }

 }