▶ 书中第四章部分程序，包括在加上自己补充的代码，图中找欧拉环
● 无向图中寻找欧拉环
package package01; import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.GraphGenerator;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.BreadthFirstPaths; public class class01
{
private Stack<Integer> cycle = new Stack<Integer>(); // 用栈来保存欧拉环的路径，栈空表示无欧拉环 private static class Edge // 图的边的结构
{
private final int v;
private final int w;
private boolean isUsed; public Edge(int v, int w)
{
this.v = v;
this.w = w;
isUsed = false;
} public int other(int vertex)
{
if (vertex == v)
return w;
if (vertex == w)
return v;
throw new IllegalArgumentException("\n<other> No such vertex.\n");
}
} public class01(Graph G)
{
if (G.E() == 0) // 至少有 1 条边
return;
for (int v = 0; v < G.V(); v++) // 欧拉环要求每个顶点的度均为偶数
{
if (G.degree(v) % 2 != 0)
return;
}
Queue<Edge>[] adj = (Queue<Edge>[]) new Queue[G.V()]; // 把邻接表每个链表转化为一个队列，以便遍历（其实可以不要？）
for (int v = 0; v < G.V(); v++)
adj[v] = new Queue<Edge>();
for (int v = 0; v < G.V(); v++)
{
boolean selfEdge = false; // 用于判断奇偶
for (int w : G.adj(v))
{
if (v == w)
{
if (!selfEdge) // 考虑某个顶点的链表出现 2k 次自己，实际只有 k 条自边，即 k 个自环
{
Edge e = new Edge(v, w);
adj[v].enqueue(e);
adj[w].enqueue(e);
}
selfEdge = !selfEdge;
}
else if (v < w) // 控制索引只添加向后顶点的边，防止重复计数
{
Edge e = new Edge(v, w);
adj[v].enqueue(e);
adj[w].enqueue(e);
}
}
}
Stack<Integer> stack = new Stack<Integer>(); // 用栈保存遍历顺序，也即欧拉环中顶点顺序
stack.push(nonIsolatedVertex(G)); // 第一个非孤立点压栈
for (cycle = new Stack<Integer>(); !stack.isEmpty();)
{
int v = stack.pop();
for (; !adj[v].isEmpty();) // 深度优先遍历
{
Edge edge = adj[v].dequeue();
if (edge.isUsed)
continue;
edge.isUsed = true; // 从 adj[v] 处改 edge(v,w) 则 adj[w] 相应顶点也变化，保证每条边只修改一次，防止回头路
stack.push(v);
v = edge.other(v);
}
cycle.push(v); // 遍历完成，把终点入栈
}
if (cycle.size() != G.E() + 1) // 存储了遍历顺序，起点终点记两次，所以比边数多 1
cycle = null;
} public Iterable<Integer> cycle()
{
return cycle;
} public boolean hasEulerianCycle()
{
return cycle != null;
} private static int nonIsolatedVertex(Graph G) // 寻找图上的第一个非独立点，也即度数大于 0 的点
{
for (int v = 0; v < G.V(); v++)
{
if (G.degree(v) > 0)
return v;
}
return -1;
} private static boolean satisfiesNecessaryAndSufficientConditions(Graph G) // 用欧拉环的充要条件进行判定
{
if (G.E() == 0) // 至少有一条边
return false;
for (int v = 0; v < G.V(); v++) // 每个顶点的度是偶数
{
if (G.degree(v) % 2 != 0)
return false;
}
BreadthFirstPaths bfs = new BreadthFirstPaths(G, nonIsolatedVertex(G)); // 图是连通的
for (int v = 0; v < G.V(); v++)
{
if (G.degree(v) > 0 && !bfs.hasPathTo(v))
return false;
}
return true;
} private static void unitTest(Graph G, String description)
{
System.out.printf("\n%s--------------------------------\n", description);
StdOut.print(G);
class01 euler = new class01(G);
System.out.printf("Eulerian cycle: ");
if (euler.hasEulerianCycle())
{
for (int v : euler.cycle())
System.out.printf(" %d", v);
}
System.out.println();
} public static void main(String[] args)
{
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]); Graph G1 = GraphGenerator.eulerianCycle(V, E);
unitTest(G1, "Eulerian cycle"); Graph G2 = GraphGenerator.eulerianPath(V, E);
unitTest(G2, "Eulerian path"); Graph G3 = new Graph(V);
unitTest(G3, "Empty graph"); Graph G4 = new Graph(V);
int v4 = StdRandom.uniform(V);
G4.addEdge(v4, v4);
unitTest(G4, "Single self loop"); Graph H1 = GraphGenerator.eulerianCycle(V / 2, E / 2); // 把两个欧拉环连在一起
Graph H2 = GraphGenerator.eulerianCycle(V - V / 2, E - E / 2);
int[] perm = new int[V];
for (int i = 0; i < V; i++)
perm[i] = i;
StdRandom.shuffle(perm);
Graph G5 = new Graph(V);
for (int v = 0; v < H1.V(); v++)
{
for (int w : H1.adj(v))
G5.addEdge(perm[v], perm[w]);
}
for (int v = 0; v < H2.V(); v++)
{
for (int w : H2.adj(v))
G5.addEdge(perm[V / 2 + v], perm[V / 2 + w]);
}
unitTest(G5, "Union of two disjoint cycles"); Graph G6 = GraphGenerator.simple(V, E);
unitTest(G6, "Random simple graph");
}
}
● 有向图中寻找欧拉环，只注释了与上面不同的地方
package package01; import java.util.Iterator;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.DigraphGenerator;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.BreadthFirstPaths; public class class01
{
private Stack<Integer> cycle = new Stack<Integer>(); public class01(Digraph G)
{
if (G.E() == 0) // 至少有一条边
return;
for (int v = 0; v < G.V(); v++) // 要求每个店的入度等于出度（否则至多为欧拉环路径，不能是环）
{
if (G.outdegree(v) != G.indegree(v))
return;
}
Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()]; // 使用迭代器而不是队列来存储
for (int v = 0; v < G.V(); v++)
adj[v] = G.adj(v).iterator();
Stack<Integer> stack = new Stack<Integer>();
for (stack.push(nonIsolatedVertex(G)); !stack.isEmpty();)
{
int v = stack.pop();
for (; adj[v].hasNext(); v = adj[v].next())
stack.push(v);
cycle.push(v);
}
if (cycle.size() != G.E() + 1)
cycle = null;
} public Iterable<Integer> cycle()
{
return cycle;
} public boolean hasEulerianCycle()
{
return cycle != null;
} private static int nonIsolatedVertex(Digraph G)
{
for (int v = 0; v < G.V(); v++)
{
if (G.outdegree(v) > 0)
return v;
}
return -1;
} private static boolean satisfiesNecessaryAndSufficientConditions(Digraph G) // 用欧拉环的充要条件进行判定
{
if (G.E() == 0) // 至少有 1 条边
return false;
for (int v = 0; v < G.V(); v++) // 每个顶点的入度等于出度
{
if (G.outdegree(v) != G.indegree(v))
return false;
}
Graph H = new Graph(G.V()); // 把图做成无向的，判断所有顶点连通
for (int v = 0; v < G.V(); v++)
{
for (int w : G.adj(v))
H.addEdge(v, w);
}
BreadthFirstPaths bfs = new BreadthFirstPaths(H, nonIsolatedVertex(G));
for (int v = 0; v < G.V(); v++)
{
if (H.degree(v) > 0 && !bfs.hasPathTo(v))
return false;
}
return true;
} private static void unitTest(Digraph G, String description)
{
System.out.printf("\n%s--------------------------------\n", description);
StdOut.print(G);
class01 euler = new class01(G);
System.out.printf("Eulerian cycle: ");
if (euler.hasEulerianCycle())
{
for (int v : euler.cycle())
System.out.printf(" %d", v);
}
StdOut.println();
} public static void main(String[] args)
{
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]); Digraph G1 = DigraphGenerator.eulerianCycle(V, E);
unitTest(G1, "Eulerian cycle"); Digraph G2 = DigraphGenerator.eulerianPath(V, E);
unitTest(G2, "Eulerian path"); Digraph G3 = new Digraph(V);
unitTest(G3, "Empty digraph"); Digraph G4 = new Digraph(V);
int v4 = StdRandom.uniform(V);
G4.addEdge(v4, v4);
unitTest(G4, "single self loop"); Digraph H1 = DigraphGenerator.eulerianCycle(V / 2, E / 2);
Digraph H2 = DigraphGenerator.eulerianCycle(V - V / 2, E - E / 2);
int[] perm = new int[V];
for (int i = 0; i < V; i++)
perm[i] = i;
StdRandom.shuffle(perm);
Digraph G5 = new Digraph(V);
for (int v = 0; v < H1.V(); v++)
{
for (int w : H1.adj(v))
G5.addEdge(perm[v], perm[w]);
}
for (int v = 0; v < H2.V(); v++)
{
for (int w : H2.adj(v))
G5.addEdge(perm[V / 2 + v], perm[V / 2 + w]);
}
unitTest(G5, "Union of two disjoint cycles"); Digraph G6 = DigraphGenerator.simple(V, E);
unitTest(G6, "Simple digraph");
/*
Digraph G7 = new Digraph(new In("eulerianD.txt"));
unitTest(G7, "4-vertex Eulerian digraph from file");
*/
}
}