▶ 书中第四章部分程序，加上自己补充的代码，随机生成各类有向图
● 随机生成有向图
1 package package01; 2 3 import edu.princeton.cs.algs4.StdOut; 4 import edu.princeton.cs.algs4.Digraph; // 多了有向图，少了集合 5 import edu.princeton.cs.algs4.SET; 6 import edu.princeton.cs.algs4.StdRandom; 7 8 public class class01 9 { 10 private static final class Edge implements Comparable<Edge> 11 { 12 private final int v; 13 private final int w; 14 15 private Edge(int v1, int v2) 16 { 17 if (v1 < v2) 18 { 19 v = v1; 20 w = v2; 21 } 22 else 23 { 24 v = v2; 25 w = v1; 26 } 27 } 28 29 public int compareTo(Edge that) 30 { 31 if (v < that.v) 32 return -1; 33 if (v > that.v) 34 return +1; 35 if (w < that.w) 36 return -1; 37 if (w > that.w) 38 return +1; 39 return 0; 40 } 41 } 42 43 private class01() {} 44 45 public static Digraph simple(int V, int E) 46 { 47 if (E < 0 || E >(long) V*(V - 1) / 2) 48 throw new IllegalArgumentException(" <simple> E < 0 || E > V(V-1)/2. "); 49 Digraph G = new Digraph(V); 50 SET<Edge> set = new SET<Edge>(); 51 for (; G.E() < E;) 52 { 53 int v = StdRandom.uniform(V); 54 int w = StdRandom.uniform(V); 55 Edge e = new Edge(v, w); 56 if ((v != w) && !set.contains(e)) 57 { 58 set.add(e); 59 G.addEdge(v, w); 60 } 61 } 62 return G; 63 } 64 65 public static Digraph simple(int V, double p) 66 { 67 if (p < 0.0 || p > 1.0) 68 throw new IllegalArgumentException(" <simple> p < 0.0 || p > 1.0. "); 69 Digraph G = new Digraph(V); 70 for (int v = 0; v < V; v++) 71 { 72 for (int w = 0; w < V; w++) // 从0 开始 73 { 74 if (v != w && StdRandom.bernoulli(p)) // 去掉自环 75 G.addEdge(v, w); 76 } 77 } 78 return G; 79 } 80 81 public static Digraph complete(int V) 82 { 83 return simple(V, 1.0); 84 } 85 86 public static Digraph dag(int V, int E) //（非均匀地）生成指定定点数和边数的有向无环图（Directed Acyclic Graph） 87 { 88 if (E < 0 || E >(long) V*(V - 1) / 2) 89 throw new IllegalArgumentException(" <dag> E < 0 || E > V1*V2. "); 90 int[] vertices = new int[V]; 91 for (int i = 0; i < V; i++) 92 vertices[i] = i; 93 StdRandom.shuffle(vertices); 94 Digraph G = new Digraph(V); 95 SET<Edge> set = new SET<Edge>(); 96 for (; G.E() < E;) 97 { 98 int i = StdRandom.uniform(V); 99 int j = StdRandom.uniform(V); 100 Edge e = new Edge(i, j); 101 if (i < j && !set.contains(e)) // 限定从索引较小的顶点指向索引较大的顶点 102 { 103 set.add(e); 104 G.addEdge(vertices[i], vertices[j]); 105 } 106 } 107 return G; 108 } 109 110 public static Digraph tournament(int V) // 生成竞赛图（任意两顶点间有一条有向边） 111 { 112 Digraph G = new Digraph(V); 113 for (int v = 0; v < G.V(); v++) 114 { 115 for (int w = v + 1; w < G.V(); w++) 116 { 117 if (StdRandom.bernoulli(0.5)) 118 G.addEdge(v, w); 119 else 120 G.addEdge(w, v); 121 } 122 } 123 return G; 124 } 125 126 public static Digraph rootedInDAG(int V, int E) // 生成有入根 DAG 图（所有链有共同的终点） 127 { 128 if (E < V - 1 || E >(long) V*(V - 1) / 2) 129 throw new IllegalArgumentException(" <rootedInDAG> E < 0 || E > V1*V2. "); 130 int[] vertices = new int[V]; 131 for (int i = 0; i < V; i++) 132 vertices[i] = i; 133 StdRandom.shuffle(vertices); 134 Digraph G = new Digraph(V); 135 SET<Edge> set = new SET<Edge>(); 136 for (int v = 0; v < V - 1; v++) // 每个点连接到索引更靠后的一个顶点上，保证每条链都收敛到最后一个顶点 137 { 138 int w = StdRandom.uniform(v + 1, V); 139 Edge e = new Edge(v, w); 140 set.add(e); 141 G.addEdge(vertices[v], vertices[w]); 142 } 143 for (; G.E() < E;) // 按靠后规则添加剩余的的边 144 { 145 int v = StdRandom.uniform(V); 146 int w = StdRandom.uniform(V); 147 Edge e = new Edge(v, w); 148 if ((v < w) && !set.contains(e)) 149 { 150 set.add(e); 151 G.addEdge(vertices[v], vertices[w]); 152 } 153 } 154 return G; 155 } 156 157 public static Digraph rootedOutDAG(int V, int E) // 生成有出根 DAG 图（所有链有相同的起点） 158 { 159 if (E < V - 1 || E >(long) V*(V - 1) / 2) 160 throw new IllegalArgumentException(" <rootedOutDAG> E < 0 || E > V1*V2. "); 161 int[] vertices = new int[V]; 162 for (int i = 0; i < V; i++) 163 vertices[i] = i; 164 StdRandom.shuffle(vertices); 165 Digraph G = new Digraph(V); 166 SET<Edge> set = new SET<Edge>(); 167 for (int v = 0; v < V - 1; v++) 168 { 169 int w = StdRandom.uniform(v + 1, V); 170 Edge e = new Edge(w, v); // 就是把 rootedInDAG 中出现 (v,w) 的地方全部换成 (v,w) 即可 171 set.add(e); 172 G.addEdge(vertices[w], vertices[v]); //换 173 } 174 for (; G.E() < E;) 175 { 176 int v = StdRandom.uniform(V); 177 int w = StdRandom.uniform(V); 178 Edge e = new Edge(w, v); // 换 179 if ((v < w) && !set.contains(e)) 180 { 181 set.add(e); 182 G.addEdge(vertices[w], vertices[v]); // 换 183 } 184 } 185 return G; 186 } 187 188 public static Digraph rootedInTree(int V) // 生成有入根树，在 rootedInDAG 的基础上限定了边数 189 { 190 return rootedInDAG(V, V - 1); 191 } 192 193 public static Digraph rootedOutTree(int V) // 生成有出根树，在 rootedOutDAG 的基础上限定了边数 194 { 195 return rootedOutDAG(V, V - 1); 196 } 197 198 public static Digraph path(int V) // 路径图，同无向版本 199 { 200 int[] vertices = new int[V]; 201 for (int i = 0; i < V; i++) 202 vertices[i] = i; 203 StdRandom.shuffle(vertices); 204 Digraph G = new Digraph(V); 205 for (int i = 0; i < V - 1; i++) 206 G.addEdge(vertices[i], vertices[i + 1]); 207 return G; 208 } 209 210 public static Digraph binaryTree(int V) // 二叉树，同无向版本 211 { 212 int[] vertices = new int[V]; 213 for (int i = 0; i < V; i++) 214 vertices[i] = i; 215 StdRandom.shuffle(vertices); 216 Digraph G = new Digraph(V); 217 for (int i = 1; i < V; i++) 218 G.addEdge(vertices[i], vertices[(i - 1) / 2]); 219 return G; 220 } 221 222 public static Digraph cycle(int V) // 环，同无向版本 223 { 224 int[] vertices = new int[V]; 225 for (int i = 0; i < V; i++) 226 vertices[i] = i; 227 StdRandom.shuffle(vertices); 228 Digraph G = new Digraph(V); 229 for (int i = 0; i < V - 1; i++) 230 G.addEdge(vertices[i], vertices[i + 1]); 231 G.addEdge(vertices[V - 1], vertices[0]); 232 return G; 233 } 234 235 public static Digraph eulerianCycle(int V, int E) // 欧拉回路，同无向版本 236 { 237 if (E <= 0 || V <= 0) 238 throw new IllegalArgumentException(" <eulerianCycle> E <= 0 || V <= 0. "); 239 int[] node = new int[E]; 240 for (int i = 0; i < E; i++) 241 node[i] = StdRandom.uniform(V); 242 Digraph G = new Digraph(V); 243 for (int i = 0; i < E - 1; i++) 244 G.addEdge(node[i], node[i + 1]); 245 G.addEdge(node[E - 1], node[0]); 246 return G; 247 } 248 249 public static Digraph eulerianPath(int V, int E) // 欧拉路径，同无向版本 250 { 251 if (E <= 0 || V <= 0) 252 throw new IllegalArgumentException(" <eulerianPath> E <= 0 || V <= 0. "); 253 int[] node = new int[E + 1]; 254 for (int i = 0; i < E + 1; i++) 255 node[i] = StdRandom.uniform(V); 256 Digraph G = new Digraph(V); 257 for (int i = 0; i < E; i++) 258 G.addEdge(node[i], node[i + 1]); 259 return G; 260 } 261 262 public static Digraph strong(int V, int E, int c) // 生成指定定点数、边数、强连通分量上限数的有向图 263 { 264 if (E <= 2 * (V - c) || E >(long) V*(V - 1) / 2 || c >= V || c <= 0) 265 throw new IllegalArgumentException(" <strong> E <= 2 * (V - c) || E > (long) V*(V - 1) / 2 || c >= V || c <= 0. "); 266 267 Digraph G = new Digraph(V); 268 SET<Edge> set = new SET<Edge>(); 269 270 int[] label = new int[V]; // 给每个顶点一个连通分量的标号 271 for (int v = 0; v < V; v++) 272 label[v] = StdRandom.uniform(c); 273 for (int i = 0; i < c; i++) // 遍历每个分量，分别生成强连通图 274 { // 原理是每个分量中挑一个根点，生成关于该点的入根树和出根树，则分量内所有顶点能以该根点为中继进行连通 275 int count = 0; // 该分量的顶点数 276 for (int v = 0; v < G.V(); v++) 277 { 278 if (label[v] == i) 279 count++; 280 } 281 int[] node = new int[count]; // 在 count 范围内用乱序数组生成子图 282 int j = 0; 283 for (int v = 0; v < V; v++) // 选出标号为 i 的所有顶点的编号 284 { 285 if (label[v] == i) 286 node[j++] = v; 287 } 288 StdRandom.shuffle(node); 289 for (int v = 0; v < count - 1; v++) // 生成一棵有入根树，根为 node[count-1] 290 { 291 int w = StdRandom.uniform(v + 1, count); 292 Edge e = new Edge(w, v); 293 set.add(e); 294 G.addEdge(node[w], node[v]); 295 } 296 for (int v = 0; v < count - 1; v++) // 生成一棵有出根树，根为 node[count-1] 297 { 298 int w = StdRandom.uniform(v + 1, count); 299 Edge e = new Edge(v, w); 300 set.add(e); 301 G.addEdge(node[v], node[w]); 302 } 303 } 304 305 for (; G.E() < E;) // 添加剩余边 306 { 307 int v = StdRandom.uniform(V); 308 int w = StdRandom.uniform(V); 309 Edge e = new Edge(v, w); 310 if (!set.contains(e) && v != w && label[v] <= label[w]) // 限制顶点的索引范围，防止出现环 311 { 312 set.add(e); 313 G.addEdge(v, w); 314 } 315 } 316 return G; 317 } 318 319 public static void main(String[] args) 320 { 321 int V = Integer.parseInt(args[0]); 322 int E = Integer.parseInt(args[1]); 323 324 StdOut.println("simple"); 325 StdOut.println(simple(V, E)); 326 327 StdOut.println("Erdos-Renyi"); 328 double p = (double)E / (V*(V - 1) / 2.0); 329 StdOut.println(simple(V, p)); 330 331 StdOut.println("complete graph"); 332 StdOut.println(complete(V)); 333 334 StdOut.println("DAG"); 335 StdOut.println(dag(V, E)); 336 337 StdOut.println("tournament"); 338 StdOut.println(tournament(V)); 339 340 StdOut.println("rooted-in DAG"); 341 StdOut.println(rootedInDAG(V, E)); 342 343 StdOut.println("rooted-out DAG"); 344 StdOut.println(rootedOutDAG(V, E)); 345 346 StdOut.println("rooted-in tree"); 347 StdOut.println(rootedInTree(V)); 348 349 StdOut.println("rooted-out DAG"); 350 StdOut.println(rootedOutTree(V)); 351 352 StdOut.println("path"); 353 StdOut.println(path(V)); 354 355 StdOut.println("binary tree"); 356 StdOut.println(binaryTree(V)); 357 358 StdOut.println("cycle"); 359 StdOut.println(cycle(V)); 360 361 StdOut.println("eulierian cycle"); 362 StdOut.println(eulerianCycle(V, E)); 363 364 StdOut.println("eulierian path"); 365 StdOut.println(eulerianPath(V, E)); 366 367 StdOut.println("strong"); 368 StdOut.println(strong(V, E, 4)); 369 } 370 }