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

▶ 书中第四章部分程序，加上自己补充的代码，随机生成各类无向图
● 随机生成无向图
  1 package package01;
  2 
  3 import edu.princeton.cs.algs4.StdOut;
  4 import edu.princeton.cs.algs4.Graph;
  5 import edu.princeton.cs.algs4.SET;
  6 import edu.princeton.cs.algs4.MinPQ;
  7 import edu.princeton.cs.algs4.StdRandom;
  8 
  9 public class class01
 10 {
 11     private static final class Edge implements Comparable<Edge>
 12     {
 13         private final int v;
 14         private final int w;
 15 
 16         private Edge(int v1, int v2)            // 输入两个顶点，保存为合适的顺序
 17         {
 18             if (v1 < v2)
 19             {
 20                 v = v1;
 21                 w = v2;
 22             }
 23             else
 24             {
 25                 v = v2;
 26                 w = v1;
 27             }
 28         }
 29 
 30         public int compareTo(Edge that)         // 边的字典序比较
 31         {
 32             if (v < that.v)
 33                 return -1;
 34             if (v > that.v)
 35                 return +1;
 36             if (w < that.w)
 37                 return -1;
 38             if (w > that.w)
 39                 return +1;
 40             return 0;
 41         }
 42     }
 43 
 44     private class01() {}
 45 
 46     public static Graph simple(int V, int E)    // 生成指定顶点数和边数的随机简单图
 47     {
 48         if (E < 0 || E >(long) V*(V - 1) / 2)
 49             throw new IllegalArgumentException("
<simple> E < 0 || E > V(V-1)/2.
");
 50         Graph G = new Graph(V);
 51         SET<Edge> set = new SET<Edge>();        // 集合用于检查新边是否与旧边相同
 52         for (; G.E() < E;)
 53         {
 54             int v = StdRandom.uniform(V);
 55             int w = StdRandom.uniform(V);
 56             Edge e = new Edge(v, w);
 57             if ((v != w) && !set.contains(e))
 58             {
 59                 set.add(e);
 60                 G.addEdge(v, w);
 61             }
 62         }
 63         return G;
 64     }
 65 
 66     public static Graph simple(int V, double p) // 生成指定定点数和边概率的随机简单图
 67     {
 68         if (p < 0.0 || p > 1.0)
 69             throw new IllegalArgumentException("
<simple> p < 0.0 || p > 1.0.
");
 70         Graph G = new Graph(V);
 71         for (int v = 0; v < V; v++)
 72         {
 73             for (int w = v + 1; w < V; w++)
 74             {
 75                 if (StdRandom.bernoulli(p))
 76                     G.addEdge(v, w);
 77             }
 78         }
 79         return G;
 80     }
 81 
 82     public static Graph complete(int V)                     // 生成指定顶点的完全图
 83     {
 84         return simple(V, 1.0);
 85     }
 86 
 87     public static Graph bipartite(int V1, int V2, int E)    // 生成指定顶点数和边数的二分图
 88     {
 89         if (E < 0 || E >(long) V1*V2)
 90             throw new IllegalArgumentException("
<bipartite> E < 0 || E > V1*V2.
");
 91         int[] vertices = new int[V1 + V2];                  // 顶点集
 92         for (int i = 0; i < V1 + V2; i++)
 93             vertices[i] = i;
 94         StdRandom.shuffle(vertices);                        // 随机化顶点序
 95         Graph G = new Graph(V1 + V2);                       // 前 V1 个点为一端，后 V2 个点为一端
 96         SET<Edge> set = new SET<Edge>();
 97         for (; G.E() < E;)
 98         {
 99             int i = StdRandom.uniform(V1);
100             int j = V1 + StdRandom.uniform(V2);
101             Edge e = new Edge(vertices[i], vertices[j]);
102             if (!set.contains(e))
103             {
104                 set.add(e);
105                 G.addEdge(vertices[i], vertices[j]);
106             }
107         }
108         return G;
109     }
110 
111     public static Graph bipartite(int V1, int V2, double p) // 生成指定顶点数和边概率的二分图
112     {
113         if (p < 0.0 || p > 1.0)
114             throw new IllegalArgumentException("
<bipartite> p < 0.0 || p > 1.0.
");
115         int[] vertices = new int[V1 + V2];
116         for (int i = 0; i < V1 + V2; i++)
117             vertices[i] = i;
118         StdRandom.shuffle(vertices);
119         Graph G = new Graph(V1 + V2);
120         for (int i = 0; i < V1; i++)
121         {
122             for (int j = V1; j < V1 + V2; j++)
123             {
124                 if (StdRandom.bernoulli(p))
125                     G.addEdge(vertices[i], vertices[j]);
126             }
127         }
128         return G;
129     }
130 
131     public static Graph completeBipartite(int V1, int V2)   // 生成完全二分图
132     {
133         return bipartite(V1, V2, V1*V2);
134     }
135 
136     public static Graph path(int V)                 // 生成指定定点数的路径图
137     {
138         int[] vertices = new int[V];                // 顶点集打乱，然后依次连起来
139         for (int i = 0; i < V; i++)
140             vertices[i] = i;
141         StdRandom.shuffle(vertices);
142         Graph G = new Graph(V);
143         for (int i = 0; i < V - 1; i++)
144             G.addEdge(vertices[i], vertices[i + 1]);
145         return G;
146     }
147 
148     public static Graph binaryTree(int V)           // 生成指定点数的二叉树
149     {
150         int[] vertices = new int[V];                // 顶点集打乱，然后每个点连接到其母顶点
151         for (int i = 0; i < V; i++)
152             vertices[i] = i;
153         StdRandom.shuffle(vertices);
154         Graph G = new Graph(V);
155         for (int i = 1; i < V; i++)
156             G.addEdge(vertices[i], vertices[(i - 1) / 2]);
157         return G;
158     }
159 
160     public static Graph cycle(int V)                // 生成指定顶点数的环
161     {
162         int[] vertices = new int[V];                // 先生成路径图，然后把终点和起点连起来
163         for (int i = 0; i < V; i++)
164             vertices[i] = i;
165         StdRandom.shuffle(vertices);
166         Graph G = new Graph(V);
167         for (int i = 0; i < V - 1; i++)
168             G.addEdge(vertices[i], vertices[i + 1]);
169         G.addEdge(vertices[V - 1], vertices[0]);
170         return G;
171     }
172 
173     public static Graph eulerianCycle(int V, int E) // 生成指顶点数和边数的欧拉回路图
174     {
175         if (E <= 0 || V <= 0)
176             throw new IllegalArgumentException("
<eulerianCycle> E <= 0 || V <= 0.
");
177         int[] node = new int[E];                    // 控制边数，去掉成环的最后一条边后应该有 E-1 边，用 E 个中继点
178         for (int i = 0; i < E; i++)
179             node[i] = StdRandom.uniform(V);
180         Graph G = new Graph(V);
181         for (int i = 0; i < E - 1; i++)
182             G.addEdge(node[i], node[i + 1]);
183         G.addEdge(node[E - 1], node[0]);            // 补上最后成环的边
184         return G;
185     }
186 
187     public static Graph eulerianPath(int V, int E)  // 生成指定顶点数和边数的欧拉路径图
188     {
189         if (E <= 0 || V <= 0)
190             throw new IllegalArgumentException("
<eulerianPath> E <= 0 || V <= 0.
");
191         int[] node = new int[E + 1];                // 控制边数，应该有 E 边，用 E+1 个中继点
192         for (int i = 0; i < E + 1; i++)
193             node[i] = StdRandom.uniform(V);
194         Graph G = new Graph(V);
195         for (int i = 0; i < E; i++)
196             G.addEdge(node[i], node[i + 1]);
197         return G;
198     }
199 
200     public static Graph wheel(int V)                // 生成指定顶点数的轮图
201     {
202         if (V <= 1)
203             throw new IllegalArgumentException("
<wheel> V <= 1.
");
204         int[] vertices = new int[V];
205         for (int i = 0; i < V; i++)
206             vertices[i] = i;
207         StdRandom.shuffle(vertices);
208         Graph G = new Graph(V);
209         for (int i = 1; i < V - 1; i++)             // 先用后 V-1 顶点生成一个环
210             G.addEdge(vertices[i], vertices[i + 1]);
211         G.addEdge(vertices[V - 1], vertices[1]);
212         for (int i = 1; i < V; i++)                 // 连接第 0 顶点和剩下的所有顶点
213             G.addEdge(vertices[0], vertices[i]);
214         return G;
215     }
216 
217     public static Graph star(int V)
218     {
219         if (V <= 1)
220             throw new IllegalArgumentException("
<wheel> V <= 1.
");
221         int[] vertices = new int[V];
222         for (int i = 0; i < V; i++)
223             vertices[i] = i;
224         StdRandom.shuffle(vertices);
225         Graph G = new Graph(V);
226         for (int i = 1; i < V; i++)                 // 连接第 0 顶点和剩下的所有顶点
227             G.addEdge(vertices[0], vertices[i]);
228         return G;
229     }
230 
231     public static Graph regular(int V, int k)       // 生成指定定点数和每个顶点的度的正则图，是简单图的概率为 e^(-k^2/4)
232     {
233         if (V*k % 2 != 0)
234             throw new IllegalArgumentException("
<regular> V*k %2 ！=0。n"); // 正则图存在的充要条件
235         int[] node = new int[V*k];                  // 生成一张 V*k 的表，每个顶点的编号出现 k 次
236         for (int i = 0; i < V; i++)
237         {
238             for (int j = 0; j < k; j++)
239                 node[V*j + i] = i;
240         }
241         StdRandom.shuffle(node);
242         Graph G = new Graph(V);
243         for (int i = 0; i < V*k / 2; i++)           // 共 V*k/2 条边，完成正则图
244             G.addEdge(node[2 * i], node[2 * i + 1]);
245         return G;
246     }
247 
248     public static Graph tree(int V)                 // 生成指定定点数的树，时间复杂度 O(V log V)
249     {                                               // http://www.proofwiki.org/wiki/Labeled_Tree_from_Prüfer_Sequence
250         Graph G = new Graph(V);                     // Cayley 定理：V顶点的标号树有 V^(V-2) 棵
251         if (V == 1)
252             return G;
253 
254         int[] prufer = new int[V - 2];              // 生成一个长为 V-2 的随机序列（双射到一棵树）
255         for (int i = 0; i < V - 2; i++)             // 最终树中，每个顶点的度数 = ("该顶点在序列中出现次数" + 1)
256             prufer[i] = StdRandom.uniform(V);
257         int[] degree = new int[V];                  // 初始化每个顶点度数 = "该顶点在序列中出现次数" + 1，后续逐渐减到 0，表示剩余度数用尽
258         for (int v = 0; v < V; v++)
259             degree[v] = 1;
260         for (int i = 0; i < V - 2; i++)
261             degree[prufer[i]]++;
262         MinPQ<Integer> pq = new MinPQ<Integer>();   // 最小优先队列保存了度数为 1 的顶点，即接下来操作中可以使用的顶点
263         for (int v = 0; v < V; v++)
264         {
265             if (degree[v] == 1)
266                 pq.insert(v);
267         }
268         for (int i = 0; i < V - 2; i++)             // 每次取队列中的一个顶点点和序列中的一个顶点，组成一条边
269         {
270             int v = pq.delMin();
271             G.addEdge(v, prufer[i]);
272             degree[v]--;                            // 更新顶点的剩余度数
273             degree[prufer[i]]--;
274             if (degree[prufer[i]] == 1)             // 更新优先队列
275                 pq.insert(prufer[i]);
276         }
277         G.addEdge(pq.delMin(), pq.delMin());        // 序列用完，优先队列中还剩最后两个顶点，组成一条边
278         return G;
279     }
280 
281     public static void main(String[] args)
282     {
283         int V = Integer.parseInt(args[0]);
284         int E = Integer.parseInt(args[1]);
285         int V1 = V / 3;
286         int V2 = V - V1;
287 
288         StdOut.println("simple");
289         StdOut.println(simple(V, E));
290 
291         StdOut.println("Erdos-Renyi");
292         double p = (double)E / (V*(V - 1) / 2.0);
293         StdOut.println(simple(V, p));
294 
295         StdOut.println("complete graph");
296         StdOut.println(complete(V));
297 
298         StdOut.println("bipartite");
299         StdOut.println(bipartite(V1, V2, E));
300 
301         StdOut.println("Erdos Renyi bipartite");
302         double q = (double)E / (V1*V2);
303         StdOut.println(bipartite(V1, V2, q));
304 
305         StdOut.println("complete bipartite");
306         StdOut.println(completeBipartite(V1, V2));
307 
308         StdOut.println("path");
309         StdOut.println(path(V));
310 
311         StdOut.println("binary tree");
312         StdOut.println(binaryTree(V));
313 
314         StdOut.println("cycle");
315         StdOut.println(cycle(V));
316 
317         StdOut.println("eulerianCycle");
318         StdOut.println(eulerianCycle(V,E));
319 
320         StdOut.println("eulerianPath");
321         StdOut.println(eulerianPath(V,E));
322 
323         StdOut.println("wheel");
324         StdOut.println(wheel(V));
325 
326         StdOut.println("star");
327         StdOut.println(star(V));
328 
329         StdOut.println("4-regular");
330         StdOut.println(regular(V, 4));
331 
332         StdOut.println("tree");
333         StdOut.println(tree(V));
334     }
335 }