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

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

● 无向图类

  1 package package01;
  2 
  3 import java.util.NoSuchElementException;
  4 import edu.princeton.cs.algs4.In;
  5 import edu.princeton.cs.algs4.StdOut;
  6 import edu.princeton.cs.algs4.Bag;
  7 import edu.princeton.cs.algs4.Stack;
  8 
  9 public class class01
 10 {
 11     private static final String NEWLINE = System.getProperty("line.separator");
 12 
 13     private final int V;
 14     private int E;
 15     private Bag<Integer>[] adj;
 16 
 17     public class01(int inputV)
 18     {
 19         if (inputV < 0)
 20             throw new IllegalArgumentException("
<Constructor> V < 0.
>");
 21         V = inputV;
 22         E = 0;
 23         adj = (Bag<Integer>[]) new Bag[V];
 24         for (int v = 0; v < V; v++)
 25             adj[v] = new Bag<Integer>();
 26     }
 27 
 28     public class01(In in)
 29     {
 30         try
 31         {
 32             V = in.readInt();
 33             if (V < 0)
 34                 throw new IllegalArgumentException("
<Constructor> V < 0.
>");
 35             adj = (Bag<Integer>[]) new Bag[V];
 36             for (int v = 0; v < V; v++)
 37                 adj[v] = new Bag<Integer>();
 38             int E = in.readInt();
 39             if (E < 0)
 40                 throw new IllegalArgumentException("
<Constructor> E < 0.
>");
 41             for (int i = 0; i < E; i++)
 42             {
 43                 int v = in.readInt();
 44                 int w = in.readInt();
 45                 //validateVertex(v);
 46                 //validateVertex(w);
 47                 addEdge(v, w);
 48             }
 49         }
 50         catch (NoSuchElementException e)
 51         {
 52             throw new IllegalArgumentException("
<Constructor> parameter error.
");
 53         }
 54     }
 55 
 56     public class01(class01 G)
 57     {
 58         this(G.V());                    // "this" 等价于 class01，即构造函数
 59         E = G.E();
 60         for (int v = 0; v < G.V(); v++) // 使用栈来遍历原图邻接表，遍历栈时建立新图的邻接表
 61         {
 62             Stack<Integer> edgeStack = new Stack<Integer>();
 63             for (int w : G.adj[v])
 64                 edgeStack.push(w);
 65             for (int w : edgeStack)
 66                 adj[v].add(w);
 67         }
 68     }
 69 
 70     public int V()
 71     {
 72         return V;
 73     }
 74 
 75     public int E()
 76     {
 77         return E;
 78     }
 79 
 80     public void addEdge(int v, int w)
 81     {
 82         //validateVertex(v);
 83         //validateVertex(w);        
 84         adj[v].add(w);
 85         adj[w].add(v);
 86         E++;
 87     }
 88 
 89     public Iterable<Integer> adj(int v) // 生成迭代器
 90     {
 91         //validateVertex(v);
 92         return adj[v];
 93     }
 94 
 95     public int degree(int v)            // 计算顶点的度数
 96     {
 97         //validateVertex(v);
 98         return adj[v].size();
 99     }
100 
101     public String toString()            // toString 接口
102     {
103         StringBuilder s = new StringBuilder();
104         s.append(V + " vertices, " + E + " edges " + NEWLINE);
105         for (int v = 0; v < V; v++)
106         {
107             s.append(v + ": ");
108             for (int w : adj[v])
109                 s.append(w + " ");
110             s.append(NEWLINE);
111         }
112         return s.toString();
113     }
114 
115     /*
116     private void validateVertex(int v)
117     {
118         if (v < 0 || v >= V)
119         throw new IllegalArgumentException("
<validateVertex> v < 0 || v >= V.
>");
120     }
121     */
122 
123     public static void main(String[] args)
124     {
125         In in = new In(args[0]);        // 输入第一行为顶点数，第二行为边数，以后每行为一条边的两个顶点
126         class01 G = new class01(in);
127         StdOut.println(G);
128     }
129 }

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

  1 package package01;
  2 
  3 import java.util.NoSuchElementException;
  4 import edu.princeton.cs.algs4.In;
  5 import edu.princeton.cs.algs4.StdOut;
  6 import edu.princeton.cs.algs4.Bag;
  7 import edu.princeton.cs.algs4.Stack;
  8 
  9 public class class01
 10 {
 11     private static final String NEWLINE = System.getProperty("line.separator");
 12 
 13     private final int V;
 14     private int E;
 15     private Bag<Integer>[] adj;
 16     private int[] indegree;         // 每个顶点的入度
 17 
 18     public class01(int inputV)
 19     {
 20         if (inputV < 0)
 21             throw new IllegalArgumentException("
<Constructor> V < 0.
>");
 22         V = inputV;
 23         E = 0;
 24         adj = (Bag<Integer>[]) new Bag[V];
 25         for (int v = 0; v < V; v++)
 26             adj[v] = new Bag<Integer>();
 27         indegree = new int[V];      // 初始化入度
 28     }
 29 
 30     public class01(In in)
 31     {
 32         try
 33         {
 34             V = in.readInt();
 35             if (V < 0)
 36                 throw new IllegalArgumentException("
<Constructor> V < 0.
>");
 37             adj = (Bag<Integer>[]) new Bag[V];
 38             for (int v = 0; v < V; v++)
 39                 adj[v] = new Bag<Integer>();
 40             int E = in.readInt();
 41             if (E < 0)
 42                 throw new IllegalArgumentException("
<Constructor> E < 0.
>");
 43             for (int i = 0; i < E; i++)
 44             {
 45                 int v = in.readInt();
 46                 int w = in.readInt();
 47                 addEdge(v, w);
 48             }
 49             indegree = new int[V];  // 初始化入度
 50         }
 51         catch (NoSuchElementException e)
 52         {
 53             throw new IllegalArgumentException("
<Constructor> parameter error.
");
 54         }
 55     }
 56 
 57     public class01(class01 G)
 58     {
 59         this(G.V());
 60         E = G.E();
 61         for (int v = 0; v < G.V(); v++)
 62         {
 63             Stack<Integer> edgeStack = new Stack<Integer>();
 64             for (int w : G.adj[v])
 65                 edgeStack.push(w);
 66             for (int w : edgeStack)
 67                 adj[v].add(w);
 68         }
 69         for (int v = 0; v < V; v++)         // 拷贝所有顶点的入度
 70             indegree[v] = G.indegree(v);
 71     }
 72 
 73     public int V()
 74     {
 75         return V;
 76     }
 77 
 78     public int E()
 79     {
 80         return E;
 81     }
 82 
 83     public void addEdge(int v, int w)
 84     {
 85         //validateVertex(v);
 86         //validateVertex(w);
 87         adj[v].add(w);
 88         indegree[w]++;                      // 添加变的时候只添加一次，并更新重点的入度
 89         E++;
 90     }
 91 
 92     public Iterable<Integer> adj(int v)
 93     {
 94         //validateVertex(v);
 95         return adj[v];
 96     }
 97 
 98     public int outdegree(int v)             // 顶点的出度
 99     {
100         //validateVertex(v);
101         return adj[v].size();
102     }
103 
104     public int indegree(int v)              // 顶点的入度 
105     {
106         //validateVertex(v);
107         return indegree[v];
108     }
109 
110     public class01 reverse()                // 反向图
111     {
112         class01 reverse = new class01(V);   // 把复制构造函数改成不用栈即可
113         for (int v = 0; v < V; v++)
114         {
115             for (int w : adj(v))
116                 reverse.addEdge(w, v);
117         }
118         return reverse;
119     }
120 
121     public String toString()
122     {
123         StringBuilder s = new StringBuilder();
124         s.append(V + " vertices, " + E + " edges " + NEWLINE);
125         for (int v = 0; v < V; v++)
126         {
127             s.append(v + ": ");
128             for (int w : adj[v])
129                 s.append(w + " ");
130             s.append(NEWLINE);
131         }
132         return s.toString();
133     }
134 
135     /*
136     private void validateVertex(int v)
137     {
138         if (v < 0 || v >= V)
139             throw new IllegalArgumentException("
<validateVertex> v < 0 || v >= V.
>");
140     }
141     */
142 
143     public static void main(String[] args)
144     {
145         In in = new In(args[0]);            // 输入第一行为顶点数，第二行为边数，以后每行依次为一条边的起点和终点
146         class01 G = new class01(in);
147         StdOut.println(G);
148     }
149 }