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

▶ 书中第四章部分程序，加上自己补充的代码，包含无向 / 有向图类

● 无向图类

 package package01;

 import java.util.NoSuchElementException;

 import edu.princeton.cs.algs4.In;

 import edu.princeton.cs.algs4.StdOut;

 import edu.princeton.cs.algs4.Bag;

 import edu.princeton.cs.algs4.Stack;

 public class class01

 {

     private static final String NEWLINE = System.getProperty("line.separator");

     private final int V;

     private int E;

     private Bag<Integer>[] adj;

     public class01(int inputV)

     {

         if (inputV < 0)

             throw new IllegalArgumentException("\n<Constructor> V < 0.\n>");

         V = inputV;

         E = 0;

         adj = (Bag<Integer>[]) new Bag[V];

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

             adj[v] = new Bag<Integer>();

     }

     public class01(In in)

     {

         try

         {

             V = in.readInt();

             if (V < 0)

                 throw new IllegalArgumentException("\n<Constructor> V < 0.\n>");

             adj = (Bag<Integer>[]) new Bag[V];

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

                 adj[v] = new Bag<Integer>();

             int E = in.readInt();

             if (E < 0)

                 throw new IllegalArgumentException("\n<Constructor> E < 0.\n>");

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

             {

                 int v = in.readInt();

                 int w = in.readInt();

                 //validateVertex(v);

                 //validateVertex(w);

                 addEdge(v, w);

             }

         }

         catch (NoSuchElementException e)

         {

             throw new IllegalArgumentException("\n<Constructor> parameter error.\n");

         }

     }

     public class01(class01 G)

     {

         this(G.V());                    // "this" 等价于 class01，即构造函数

         E = G.E();

         for (int v = 0; v < G.V(); v++) // 使用栈来遍历原图邻接表，遍历栈时建立新图的邻接表

         {

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

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

                 edgeStack.push(w);

             for (int w : edgeStack)

                 adj[v].add(w);

         }

     }

     public int V()

     {

         return V;

     }

     public int E()

     {

         return E;

     }

     public void addEdge(int v, int w)

     {

         //validateVertex(v);

         //validateVertex(w);

         adj[v].add(w);

         adj[w].add(v);

         E++;

     }

     public Iterable<Integer> adj(int v) // 生成迭代器

     {

         //validateVertex(v);

         return adj[v];

     }

     public int degree(int v)            // 计算顶点的度数

     {

         //validateVertex(v);

         return adj[v].size();

     }

     public String toString()            // toString 接口

     {

         StringBuilder s = new StringBuilder();

         s.append(V + " vertices, " + E + " edges " + NEWLINE);

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

         {

             s.append(v + ": ");

             for (int w : adj[v])

                 s.append(w + " ");

             s.append(NEWLINE);

         }

         return s.toString();

     }

     /*

     private void validateVertex(int v)

     {

         if (v < 0 || v >= V)

         throw new IllegalArgumentException("\n<validateVertex> v < 0 || v >= V.\n>");

     }

     */

     public static void main(String[] args)

     {

         In in = new In(args[0]);        // 输入第一行为顶点数，第二行为边数，以后每行为一条边的两个顶点

         class01 G = new class01(in);

         StdOut.println(G);

     }

 }

● 有向图类，只注释了与无向图不同的地方

 package package01;

 import java.util.NoSuchElementException;

 import edu.princeton.cs.algs4.In;

 import edu.princeton.cs.algs4.StdOut;

 import edu.princeton.cs.algs4.Bag;

 import edu.princeton.cs.algs4.Stack;

 public class class01

 {

     private static final String NEWLINE = System.getProperty("line.separator");

     private final int V;

     private int E;

     private Bag<Integer>[] adj;

     private int[] indegree;         // 每个顶点的入度

     public class01(int inputV)

     {

         if (inputV < 0)

             throw new IllegalArgumentException("\n<Constructor> V < 0.\n>");

         V = inputV;

         E = 0;

         adj = (Bag<Integer>[]) new Bag[V];

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

             adj[v] = new Bag<Integer>();

         indegree = new int[V];      // 初始化入度

     }

     public class01(In in)

     {

         try

         {

             V = in.readInt();

             if (V < 0)

                 throw new IllegalArgumentException("\n<Constructor> V < 0.\n>");

             adj = (Bag<Integer>[]) new Bag[V];

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

                 adj[v] = new Bag<Integer>();

             int E = in.readInt();

             if (E < 0)

                 throw new IllegalArgumentException("\n<Constructor> E < 0.\n>");

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

             {

                 int v = in.readInt();

                 int w = in.readInt();

                 addEdge(v, w);

             }

             indegree = new int[V];  // 初始化入度

         }

         catch (NoSuchElementException e)

         {

             throw new IllegalArgumentException("\n<Constructor> parameter error.\n");

         }

     }

     public class01(class01 G)

     {

         this(G.V());

         E = G.E();

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

         {

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

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

                 edgeStack.push(w);

             for (int w : edgeStack)

                 adj[v].add(w);

         }

         for (int v = 0; v < V; v++)         // 拷贝所有顶点的入度

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

     }

     public int V()

     {

         return V;

     }

     public int E()

     {

         return E;

     }

     public void addEdge(int v, int w)

     {

         //validateVertex(v);

         //validateVertex(w);

         adj[v].add(w);

         indegree[w]++;                      // 添加变的时候只添加一次，并更新重点的入度

         E++;

     }

     public Iterable<Integer> adj(int v)

     {

         //validateVertex(v);

         return adj[v];

     }

     public int outdegree(int v)             // 顶点的出度

     {

         //validateVertex(v);

         return adj[v].size();

     }

     public int indegree(int v)              // 顶点的入度

     {

         //validateVertex(v);

         return indegree[v];

     }

     public class01 reverse()                // 反向图

     {

         class01 reverse = new class01(V);   // 把复制构造函数改成不用栈即可

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

         {

             for (int w : adj(v))

                 reverse.addEdge(w, v);

         }

         return reverse;

     }

     public String toString()

     {

         StringBuilder s = new StringBuilder();

         s.append(V + " vertices, " + E + " edges " + NEWLINE);

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

         {

             s.append(v + ": ");

             for (int w : adj[v])

                 s.append(w + " ");

             s.append(NEWLINE);

         }

         return s.toString();

     }

     /*

     private void validateVertex(int v)

     {

         if (v < 0 || v >= V)

             throw new IllegalArgumentException("\n<validateVertex> v < 0 || v >= V.\n>");

     }

     */

     public static void main(String[] args)

     {

         In in = new In(args[0]);            // 输入第一行为顶点数，第二行为边数，以后每行依次为一条边的起点和终点

         class01 G = new class01(in);

         StdOut.println(G);

     }

 }