▶ 书中第四章部分程序，包括在加上自己补充的代码，图中找欧拉路径
● 无向图中寻找欧拉路径，只注释了与欧拉环不同的地方
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)
return;
int oddDegreeVertices = 0; // 记录奇数度点的数量
int s = nonIsolatedVertex(G); // 选一个非孤立点为起点，有奇数度点的话要更换
if (G.E() == 0) // 认为无边的图也存在欧拉路径，这与欧拉环不同
s = 0;
else // 其他情况照常处理
{
for (int v = 0; v < G.V(); v++)
{
if (G.degree(v) % 2 != 0)
{
oddDegreeVertices++;
s = v;
}
}
if (oddDegreeVertices > 2) // 奇数度点多于 2，不存在欧拉路径
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)
{
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(s);
for (path = 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;
stack.push(v);
v = edge.other(v);
}
path.push(v);
}
if (path.size() != G.E() + 1)
path = null;
} public Iterable<Integer> path()
{
return path;
} public boolean hasEulerianPath()
{
return path != null;
} private static int nonIsolatedVertex(Graph G)
{
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 true;
int oddDegreeVertices = 0;
for (int v = 0; v < G.V(); v++)
{
if (G.degree(v) % 2 != 0)
oddDegreeVertices++;
}
if (oddDegreeVertices > 2)
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 path: ");
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(G2);
G3.addEdge(StdRandom.uniform(V), StdRandom.uniform(V));
unitTest(G3, "one random edge added to Eulerian path"); Graph G4 = new Graph(V);
int v4 = StdRandom.uniform(V);
G4.addEdge(v4, v4);
unitTest(G4, "single self loop"); Graph G5 = new Graph(V);
G5.addEdge(StdRandom.uniform(V), StdRandom.uniform(V));
unitTest(G5, "single edge"); Graph G6 = new Graph(V);
unitTest(G6, "empty graph"); Graph G7 = GraphGenerator.simple(V, E);
unitTest(G7, "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> path = null; public class01(Digraph G)
{
int s = nonIsolatedVertex(G);
if (s == -1) // 没有边
s = 0;
else
{
int deficit = 0; // 统计所有顶点总出度与总入度的差
for (int v = 0; v < G.V(); v++)
{
if (G.outdegree(v) > G.indegree(v)) // 计算 deficit 不能直接加总出度和入度的差
{ // 因为平行边不影响 G.outdegree(v) - G.indegree(v)，但会导致不存在欧拉路径
deficit += (G.outdegree(v) - G.indegree(v));
s = v;
}
}
if (deficit > 1) // 差大于 1 则不存在欧拉路径
return;
}
path = new Stack<Integer>();
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(s); !stack.isEmpty(); )
{
int v = stack.pop();
for (; adj[v].hasNext(); v = adj[v].next())
stack.push(v);
path.push(v);
}
if (path.size() != G.E() + 1)
path = null;
} public Iterable<Integer> path()
{
return path;
} public boolean hasEulerianPath()
{
return path != 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)
return true;
int deficit = 0;
for (int v = 0; v < G.V(); v++)
{
if (G.outdegree(v) > G.indegree(v))
deficit += (G.outdegree(v) - G.indegree(v));
}
if (deficit > 1)
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 path: ");
if (euler.hasEulerianPath())
{
for (int v : euler.path())
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(G2);
G3.addEdge(StdRandom.uniform(V), StdRandom.uniform(V));
unitTest(G3, "one random edge added to Eulerian path"); Digraph G4 = new Digraph(V);
int v4 = StdRandom.uniform(V);
G4.addEdge(v4, v4);
unitTest(G4, "single self loop"); Digraph G5 = new Digraph(V);
G5.addEdge(StdRandom.uniform(V), StdRandom.uniform(V));
unitTest(G5, "single edge"); Digraph G6 = new Digraph(V);
unitTest(G6, "empty digraph"); Digraph G7 = DigraphGenerator.simple(V, E);
unitTest(G7, "simple digraph");
}
}