▶ 书中第四章部分程序，加上自己补充的代码，随机生成各类有向图
● 随机生成有向图
package package01; import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Digraph; // 多了有向图，少了集合
import edu.princeton.cs.algs4.SET;
import edu.princeton.cs.algs4.StdRandom; public class class01
{
private static final class Edge implements Comparable<Edge>
{
private final int v;
private final int w; private Edge(int v1, int v2)
{
if (v1 < v2)
{
v = v1;
w = v2;
}
else
{
v = v2;
w = v1;
}
} public int compareTo(Edge that)
{
if (v < that.v)
return -1;
if (v > that.v)
return +1;
if (w < that.w)
return -1;
if (w > that.w)
return +1;
return 0;
}
} private class01() {} public static Digraph simple(int V, int E)
{
if (E < 0 || E >(long) V*(V - 1) / 2)
throw new IllegalArgumentException("\n<simple> E < 0 || E > V(V-1)/2.\n");
Digraph G = new Digraph(V);
SET<Edge> set = new SET<Edge>();
for (; G.E() < E;)
{
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
Edge e = new Edge(v, w);
if ((v != w) && !set.contains(e))
{
set.add(e);
G.addEdge(v, w);
}
}
return G;
} public static Digraph simple(int V, double p)
{
if (p < 0.0 || p > 1.0)
throw new IllegalArgumentException("\n<simple> p < 0.0 || p > 1.0.\n");
Digraph G = new Digraph(V);
for (int v = 0; v < V; v++)
{
for (int w = 0; w < V; w++) // 从0 开始
{
if (v != w && StdRandom.bernoulli(p)) // 去掉自环
G.addEdge(v, w);
}
}
return G;
} public static Digraph complete(int V)
{
return simple(V, 1.0);
} public static Digraph dag(int V, int E) //（非均匀地）生成指定定点数和边数的有向无环图（Directed Acyclic Graph）
{
if (E < 0 || E >(long) V*(V - 1) / 2)
throw new IllegalArgumentException("\n<dag> E < 0 || E > V1*V2.\n");
int[] vertices = new int[V];
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Digraph G = new Digraph(V);
SET<Edge> set = new SET<Edge>();
for (; G.E() < E;)
{
int i = StdRandom.uniform(V);
int j = StdRandom.uniform(V);
Edge e = new Edge(i, j);
if (i < j && !set.contains(e)) // 限定从索引较小的顶点指向索引较大的顶点
{
set.add(e);
G.addEdge(vertices[i], vertices[j]);
}
}
return G;
} public static Digraph tournament(int V) // 生成竞赛图（任意两顶点间有一条有向边）
{
Digraph G = new Digraph(V);
for (int v = 0; v < G.V(); v++)
{
for (int w = v + 1; w < G.V(); w++)
{
if (StdRandom.bernoulli(0.5))
G.addEdge(v, w);
else
G.addEdge(w, v);
}
}
return G;
} public static Digraph rootedInDAG(int V, int E) // 生成有入根 DAG 图（所有链有共同的终点）
{
if (E < V - 1 || E >(long) V*(V - 1) / 2)
throw new IllegalArgumentException("\n<rootedInDAG> E < 0 || E > V1*V2.\n");
int[] vertices = new int[V];
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Digraph G = new Digraph(V);
SET<Edge> set = new SET<Edge>();
for (int v = 0; v < V - 1; v++) // 每个点连接到索引更靠后的一个顶点上，保证每条链都收敛到最后一个顶点
{
int w = StdRandom.uniform(v + 1, V);
Edge e = new Edge(v, w);
set.add(e);
G.addEdge(vertices[v], vertices[w]);
}
for (; G.E() < E;) // 按靠后规则添加剩余的的边
{
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
Edge e = new Edge(v, w);
if ((v < w) && !set.contains(e))
{
set.add(e);
G.addEdge(vertices[v], vertices[w]);
}
}
return G;
} public static Digraph rootedOutDAG(int V, int E) // 生成有出根 DAG 图（所有链有相同的起点）
{
if (E < V - 1 || E >(long) V*(V - 1) / 2)
throw new IllegalArgumentException("\n<rootedOutDAG> E < 0 || E > V1*V2.\n");
int[] vertices = new int[V];
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Digraph G = new Digraph(V);
SET<Edge> set = new SET<Edge>();
for (int v = 0; v < V - 1; v++)
{
int w = StdRandom.uniform(v + 1, V);
Edge e = new Edge(w, v); // 就是把 rootedInDAG 中出现 (v,w) 的地方全部换成 (v,w) 即可
set.add(e);
G.addEdge(vertices[w], vertices[v]); //换
}
for (; G.E() < E;)
{
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
Edge e = new Edge(w, v); // 换
if ((v < w) && !set.contains(e))
{
set.add(e);
G.addEdge(vertices[w], vertices[v]); // 换
}
}
return G;
} public static Digraph rootedInTree(int V) // 生成有入根树，在 rootedInDAG 的基础上限定了边数
{
return rootedInDAG(V, V - 1);
} public static Digraph rootedOutTree(int V) // 生成有出根树，在 rootedOutDAG 的基础上限定了边数
{
return rootedOutDAG(V, V - 1);
} public static Digraph path(int V) // 路径图，同无向版本
{
int[] vertices = new int[V];
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Digraph G = new Digraph(V);
for (int i = 0; i < V - 1; i++)
G.addEdge(vertices[i], vertices[i + 1]);
return G;
} public static Digraph binaryTree(int V) // 二叉树，同无向版本
{
int[] vertices = new int[V];
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Digraph G = new Digraph(V);
for (int i = 1; i < V; i++)
G.addEdge(vertices[i], vertices[(i - 1) / 2]);
return G;
} public static Digraph cycle(int V) // 环，同无向版本
{
int[] vertices = new int[V];
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Digraph G = new Digraph(V);
for (int i = 0; i < V - 1; i++)
G.addEdge(vertices[i], vertices[i + 1]);
G.addEdge(vertices[V - 1], vertices[0]);
return G;
} public static Digraph eulerianCycle(int V, int E) // 欧拉回路，同无向版本
{
if (E <= 0 || V <= 0)
throw new IllegalArgumentException("\n<eulerianCycle> E <= 0 || V <= 0.\n");
int[] node = new int[E];
for (int i = 0; i < E; i++)
node[i] = StdRandom.uniform(V);
Digraph G = new Digraph(V);
for (int i = 0; i < E - 1; i++)
G.addEdge(node[i], node[i + 1]);
G.addEdge(node[E - 1], node[0]);
return G;
} public static Digraph eulerianPath(int V, int E) // 欧拉路径，同无向版本
{
if (E <= 0 || V <= 0)
throw new IllegalArgumentException("\n<eulerianPath> E <= 0 || V <= 0.\n");
int[] node = new int[E + 1];
for (int i = 0; i < E + 1; i++)
node[i] = StdRandom.uniform(V);
Digraph G = new Digraph(V);
for (int i = 0; i < E; i++)
G.addEdge(node[i], node[i + 1]);
return G;
} public static Digraph strong(int V, int E, int c) // 生成指定定点数、边数、强连通分量上限数的有向图
{
if (E <= 2 * (V - c) || E >(long) V*(V - 1) / 2 || c >= V || c <= 0)
throw new IllegalArgumentException("\n<strong> E <= 2 * (V - c) || E > (long) V*(V - 1) / 2 || c >= V || c <= 0.\n"); Digraph G = new Digraph(V);
SET<Edge> set = new SET<Edge>(); int[] label = new int[V]; // 给每个顶点一个连通分量的标号
for (int v = 0; v < V; v++)
label[v] = StdRandom.uniform(c);
for (int i = 0; i < c; i++) // 遍历每个分量，分别生成强连通图
{ // 原理是每个分量中挑一个根点，生成关于该点的入根树和出根树，则分量内所有顶点能以该根点为中继进行连通
int count = 0; // 该分量的顶点数
for (int v = 0; v < G.V(); v++)
{
if (label[v] == i)
count++;
}
int[] node = new int[count]; // 在 count 范围内用乱序数组生成子图
int j = 0;
for (int v = 0; v < V; v++) // 选出标号为 i 的所有顶点的编号
{
if (label[v] == i)
node[j++] = v;
}
StdRandom.shuffle(node);
for (int v = 0; v < count - 1; v++) // 生成一棵有入根树，根为 node[count-1]
{
int w = StdRandom.uniform(v + 1, count);
Edge e = new Edge(w, v);
set.add(e);
G.addEdge(node[w], node[v]);
}
for (int v = 0; v < count - 1; v++) // 生成一棵有出根树，根为 node[count-1]
{
int w = StdRandom.uniform(v + 1, count);
Edge e = new Edge(v, w);
set.add(e);
G.addEdge(node[v], node[w]);
}
} for (; G.E() < E;) // 添加剩余边
{
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
Edge e = new Edge(v, w);
if (!set.contains(e) && v != w && label[v] <= label[w]) // 限制顶点的索引范围，防止出现环
{
set.add(e);
G.addEdge(v, w);
}
}
return G;
} public static void main(String[] args)
{
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]); StdOut.println("simple");
StdOut.println(simple(V, E)); StdOut.println("Erdos-Renyi");
double p = (double)E / (V*(V - 1) / 2.0);
StdOut.println(simple(V, p)); StdOut.println("complete graph");
StdOut.println(complete(V)); StdOut.println("DAG");
StdOut.println(dag(V, E)); StdOut.println("tournament");
StdOut.println(tournament(V)); StdOut.println("rooted-in DAG");
StdOut.println(rootedInDAG(V, E)); StdOut.println("rooted-out DAG");
StdOut.println(rootedOutDAG(V, E)); StdOut.println("rooted-in tree");
StdOut.println(rootedInTree(V)); StdOut.println("rooted-out DAG");
StdOut.println(rootedOutTree(V)); StdOut.println("path");
StdOut.println(path(V)); StdOut.println("binary tree");
StdOut.println(binaryTree(V)); StdOut.println("cycle");
StdOut.println(cycle(V)); StdOut.println("eulierian cycle");
StdOut.println(eulerianCycle(V, E)); StdOut.println("eulierian path");
StdOut.println(eulerianPath(V, E)); StdOut.println("strong");
StdOut.println(strong(V, E, 4));
}
}