《算法》第四章部分程序 part 8

▶ 书中第四章部分程序，包括在加上自己补充的代码，图中找欧拉路径

● 无向图中寻找欧拉路径，只注释了与欧拉环不同的地方

 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");

     }

 }