▶ 书中第四章部分程序，加上自己补充的代码，随机生成各类无向图
● 随机生成无向图
package package01; import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.SET;
import edu.princeton.cs.algs4.MinPQ;
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 Graph 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");
Graph G = new Graph(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 Graph simple(int V, double p) // 生成指定定点数和边概率的随机简单图
{
if (p < 0.0 || p > 1.0)
throw new IllegalArgumentException("\n<simple> p < 0.0 || p > 1.0.\n");
Graph G = new Graph(V);
for (int v = 0; v < V; v++)
{
for (int w = v + 1; w < V; w++)
{
if (StdRandom.bernoulli(p))
G.addEdge(v, w);
}
}
return G;
} public static Graph complete(int V) // 生成指定顶点的完全图
{
return simple(V, 1.0);
} public static Graph bipartite(int V1, int V2, int E) // 生成指定顶点数和边数的二分图
{
if (E < 0 || E >(long) V1*V2)
throw new IllegalArgumentException("\n<bipartite> E < 0 || E > V1*V2.\n");
int[] vertices = new int[V1 + V2]; // 顶点集
for (int i = 0; i < V1 + V2; i++)
vertices[i] = i;
StdRandom.shuffle(vertices); // 随机化顶点序
Graph G = new Graph(V1 + V2); // 前 V1 个点为一端，后 V2 个点为一端
SET<Edge> set = new SET<Edge>();
for (; G.E() < E;)
{
int i = StdRandom.uniform(V1);
int j = V1 + StdRandom.uniform(V2);
Edge e = new Edge(vertices[i], vertices[j]);
if (!set.contains(e))
{
set.add(e);
G.addEdge(vertices[i], vertices[j]);
}
}
return G;
} public static Graph bipartite(int V1, int V2, double p) // 生成指定顶点数和边概率的二分图
{
if (p < 0.0 || p > 1.0)
throw new IllegalArgumentException("\n<bipartite> p < 0.0 || p > 1.0.\n");
int[] vertices = new int[V1 + V2];
for (int i = 0; i < V1 + V2; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Graph G = new Graph(V1 + V2);
for (int i = 0; i < V1; i++)
{
for (int j = V1; j < V1 + V2; j++)
{
if (StdRandom.bernoulli(p))
G.addEdge(vertices[i], vertices[j]);
}
}
return G;
} public static Graph completeBipartite(int V1, int V2) // 生成完全二分图
{
return bipartite(V1, V2, V1*V2);
} public static Graph path(int V) // 生成指定定点数的路径图
{
int[] vertices = new int[V]; // 顶点集打乱，然后依次连起来
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Graph G = new Graph(V);
for (int i = 0; i < V - 1; i++)
G.addEdge(vertices[i], vertices[i + 1]);
return G;
} public static Graph binaryTree(int V) // 生成指定点数的二叉树
{
int[] vertices = new int[V]; // 顶点集打乱，然后每个点连接到其母顶点
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Graph G = new Graph(V);
for (int i = 1; i < V; i++)
G.addEdge(vertices[i], vertices[(i - 1) / 2]);
return G;
} public static Graph cycle(int V) // 生成指定顶点数的环
{
int[] vertices = new int[V]; // 先生成路径图，然后把终点和起点连起来
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Graph G = new Graph(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 Graph 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]; // 控制边数，去掉成环的最后一条边后应该有 E-1 边，用 E 个中继点
for (int i = 0; i < E; i++)
node[i] = StdRandom.uniform(V);
Graph G = new Graph(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 Graph 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]; // 控制边数，应该有 E 边，用 E+1 个中继点
for (int i = 0; i < E + 1; i++)
node[i] = StdRandom.uniform(V);
Graph G = new Graph(V);
for (int i = 0; i < E; i++)
G.addEdge(node[i], node[i + 1]);
return G;
} public static Graph wheel(int V) // 生成指定顶点数的轮图
{
if (V <= 1)
throw new IllegalArgumentException("\n<wheel> V <= 1.\n");
int[] vertices = new int[V];
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Graph G = new Graph(V);
for (int i = 1; i < V - 1; i++) // 先用后 V-1 顶点生成一个环
G.addEdge(vertices[i], vertices[i + 1]);
G.addEdge(vertices[V - 1], vertices[1]);
for (int i = 1; i < V; i++) // 连接第 0 顶点和剩下的所有顶点
G.addEdge(vertices[0], vertices[i]);
return G;
} public static Graph star(int V)
{
if (V <= 1)
throw new IllegalArgumentException("\n<wheel> V <= 1.\n");
int[] vertices = new int[V];
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
Graph G = new Graph(V);
for (int i = 1; i < V; i++) // 连接第 0 顶点和剩下的所有顶点
G.addEdge(vertices[0], vertices[i]);
return G;
} public static Graph regular(int V, int k) // 生成指定定点数和每个顶点的度的正则图，是简单图的概率为 e^(-k^2/4)
{
if (V*k % 2 != 0)
throw new IllegalArgumentException("\n<regular> V*k %2 ！=0。n"); // 正则图存在的充要条件
int[] node = new int[V*k]; // 生成一张 V*k 的表，每个顶点的编号出现 k 次
for (int i = 0; i < V; i++)
{
for (int j = 0; j < k; j++)
node[V*j + i] = i;
}
StdRandom.shuffle(node);
Graph G = new Graph(V);
for (int i = 0; i < V*k / 2; i++) // 共 V*k/2 条边，完成正则图
G.addEdge(node[2 * i], node[2 * i + 1]);
return G;
} public static Graph tree(int V) // 生成指定定点数的树，时间复杂度 O(V log V)
{ // http://www.proofwiki.org/wiki/Labeled_Tree_from_Prüfer_Sequence
Graph G = new Graph(V); // Cayley 定理：V顶点的标号树有 V^(V-2) 棵
if (V == 1)
return G; int[] prufer = new int[V - 2]; // 生成一个长为 V-2 的随机序列（双射到一棵树）
for (int i = 0; i < V - 2; i++) // 最终树中，每个顶点的度数 = ("该顶点在序列中出现次数" + 1)
prufer[i] = StdRandom.uniform(V);
int[] degree = new int[V]; // 初始化每个顶点度数 = "该顶点在序列中出现次数" + 1，后续逐渐减到 0，表示剩余度数用尽
for (int v = 0; v < V; v++)
degree[v] = 1;
for (int i = 0; i < V - 2; i++)
degree[prufer[i]]++;
MinPQ<Integer> pq = new MinPQ<Integer>(); // 最小优先队列保存了度数为 1 的顶点，即接下来操作中可以使用的顶点
for (int v = 0; v < V; v++)
{
if (degree[v] == 1)
pq.insert(v);
}
for (int i = 0; i < V - 2; i++) // 每次取队列中的一个顶点点和序列中的一个顶点，组成一条边
{
int v = pq.delMin();
G.addEdge(v, prufer[i]);
degree[v]--; // 更新顶点的剩余度数
degree[prufer[i]]--;
if (degree[prufer[i]] == 1) // 更新优先队列
pq.insert(prufer[i]);
}
G.addEdge(pq.delMin(), pq.delMin()); // 序列用完，优先队列中还剩最后两个顶点，组成一条边
return G;
} public static void main(String[] args)
{
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]);
int V1 = V / 3;
int V2 = V - V1; 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("bipartite");
StdOut.println(bipartite(V1, V2, E)); StdOut.println("Erdos Renyi bipartite");
double q = (double)E / (V1*V2);
StdOut.println(bipartite(V1, V2, q)); StdOut.println("complete bipartite");
StdOut.println(completeBipartite(V1, V2)); StdOut.println("path");
StdOut.println(path(V)); StdOut.println("binary tree");
StdOut.println(binaryTree(V)); StdOut.println("cycle");
StdOut.println(cycle(V)); StdOut.println("eulerianCycle");
StdOut.println(eulerianCycle(V,E)); StdOut.println("eulerianPath");
StdOut.println(eulerianPath(V,E)); StdOut.println("wheel");
StdOut.println(wheel(V)); StdOut.println("star");
StdOut.println(star(V)); StdOut.println("4-regular");
StdOut.println(regular(V, 4)); StdOut.println("tree");
StdOut.println(tree(V));
}
}