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

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

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

  1 package package01;
  2 
  3 import edu.princeton.cs.algs4.StdOut;
  4 import edu.princeton.cs.algs4.StdRandom;
  5 import edu.princeton.cs.algs4.GraphGenerator;
  6 import edu.princeton.cs.algs4.Graph;
  7 import edu.princeton.cs.algs4.Stack;
  8 import edu.princeton.cs.algs4.Queue;
  9 import edu.princeton.cs.algs4.BreadthFirstPaths;
 10 
 11 public class class01
 12 {
 13     private Stack<Integer> cycle = new Stack<Integer>();
 14 
 15     private static class Edge
 16     {
 17         private final int v;
 18         private final int w;
 19         private boolean isUsed;
 20 
 21         public Edge(int v, int w)
 22         {
 23             this.v = v;
 24             this.w = w;
 25             isUsed = false;
 26         }
 27 
 28         public int other(int vertex)
 29         {
 30             if (vertex == v)
 31                 return w;
 32             if (vertex == w)
 33                 return v;
 34             throw new IllegalArgumentException("
<other> No such vertex.
");
 35         }
 36     }
 37 
 38     public class01(Graph G)
 39     {
 40         if (G.E() == 0)
 41             return;
 42         int oddDegreeVertices = 0;          // 记录奇数度点的数量       
 43         int s = nonIsolatedVertex(G);       // 选一个非孤立点为起点，有奇数度点的话要更换
 44         if (G.E() == 0)                     // 认为无边的图也存在欧拉路径，这与欧拉环不同
 45             s = 0;
 46         else                                // 其他情况照常处理
 47         {
 48             for (int v = 0; v < G.V(); v++)
 49             {
 50                 if (G.degree(v) % 2 != 0)
 51                 {
 52                     oddDegreeVertices++;
 53                     s = v;
 54                 }
 55             }
 56             if (oddDegreeVertices > 2)      // 奇数度点多于 2，不存在欧拉路径
 57                 return;
 58             Queue<Edge>[] adj = (Queue<Edge>[]) new Queue[G.V()];
 59             for (int v = 0; v < G.V(); v++)
 60                 adj[v] = new Queue<Edge>();
 61             for (int v = 0; v < G.V(); v++)
 62             {
 63                 boolean selfEdge = false;
 64                 for (int w : G.adj(v))
 65                 {
 66                     if (v == w)
 67                     {
 68                         if (!selfEdge)
 69                         {
 70                             Edge e = new Edge(v, w);
 71                             adj[v].enqueue(e);
 72                             adj[w].enqueue(e);
 73                         }
 74                         selfEdge = !selfEdge;
 75                     }
 76                     else if (v < w)
 77                     {
 78                         Edge e = new Edge(v, w);
 79                         adj[v].enqueue(e);
 80                         adj[w].enqueue(e);
 81                     }
 82                 }
 83             }
 84         }
 85         Stack<Integer> stack = new Stack<Integer>();
 86         stack.push(s);
 87         for (path = new Stack<Integer>(); !stack.isEmpty();)
 88         {
 89             int v = stack.pop();
 90             for (; !adj[v].isEmpty();)
 91             {
 92                 Edge edge = adj[v].dequeue();
 93                 if (edge.isUsed)
 94                     continue;
 95                 edge.isUsed = true;
 96                 stack.push(v);
 97                 v = edge.other(v);
 98             }
 99             path.push(v);
100         }
101         if (path.size() != G.E() + 1)
102             path = null;
103     }
104 
105     public Iterable<Integer> path()
106     {
107         return path;
108     }
109 
110     public boolean hasEulerianPath()
111     {
112         return path != null;
113     }
114 
115     private static int nonIsolatedVertex(Graph G)
116     {
117         for (int v = 0; v < G.V(); v++)
118         {
119             if (G.degree(v) > 0)
120                 return v;
121         }
122         return -1;
123     }
124 
125     private static boolean satisfiesNecessaryAndSufficientConditions(Graph G)
126     {
127         if (G.E() == 0)                     // 认为没有变的图也有欧拉路径，统计奇数度的顶点
128             return true;
129         int oddDegreeVertices = 0;
130         for (int v = 0; v < G.V(); v++)
131         {
132             if (G.degree(v) % 2 != 0)
133                 oddDegreeVertices++;
134         }
135         if (oddDegreeVertices > 2)
136             return false;
137         BreadthFirstPaths bfs = new BreadthFirstPaths(G, nonIsolatedVertex(G));
138         for (int v = 0; v < G.V(); v++)
139         {
140             if (G.degree(v) > 0 && !bfs.hasPathTo(v))
141                 return false;
142         }
143         return true;
144     }
145 
146     private static void unitTest(Graph G, String description)
147     {
148         System.out.printf("
%s--------------------------------
", description);
149         StdOut.print(G);
150         class01 euler = new class01(G);
151         System.out.printf("Eulerian path: ");
152         if (euler.hasEulerianCycle())
153         {
154             for (int v : euler.cycle())
155                 System.out.printf(" %d", v);
156         }
157         System.out.println();
158     }
159 
160     public static void main(String[] args)
161     {
162         int V = Integer.parseInt(args[0]);
163         int E = Integer.parseInt(args[1]);
164 
165         Graph G1 = GraphGenerator.eulerianCycle(V, E);
166         unitTest(G1, "Eulerian cycle");
167 
168         Graph G2 = GraphGenerator.eulerianPath(V, E);
169         unitTest(G2, "Eulerian path");
170 
171         Graph G3 = new Graph(G2);
172         G3.addEdge(StdRandom.uniform(V), StdRandom.uniform(V));
173         unitTest(G3, "one random edge added to Eulerian path");
174 
175         Graph G4 = new Graph(V);
176         int v4 = StdRandom.uniform(V);
177         G4.addEdge(v4, v4);
178         unitTest(G4, "single self loop");
179 
180         Graph G5 = new Graph(V);
181         G5.addEdge(StdRandom.uniform(V), StdRandom.uniform(V));
182         unitTest(G5, "single edge");
183 
184         Graph G6 = new Graph(V);
185         unitTest(G6, "empty graph");
186 
187         Graph G7 = GraphGenerator.simple(V, E);
188         unitTest(G7, "simple graph");
189     }
190 }

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

  1 package package01;
  2 
  3 import java.util.Iterator;
  4 import edu.princeton.cs.algs4.StdOut;
  5 import edu.princeton.cs.algs4.StdRandom;
  6 import edu.princeton.cs.algs4.DigraphGenerator;
  7 import edu.princeton.cs.algs4.Graph;
  8 import edu.princeton.cs.algs4.Digraph;
  9 import edu.princeton.cs.algs4.Stack;
 10 import edu.princeton.cs.algs4.BreadthFirstPaths;
 11 
 12 public class class01
 13 {
 14     private Stack<Integer> path = null;
 15 
 16     public class01(Digraph G)
 17     {
 18         int s = nonIsolatedVertex(G);
 19         if (s == -1)                                                // 没有边
 20             s = 0;
 21         else
 22         {
 23             int deficit = 0;                                        // 统计所有顶点总出度与总入度的差
 24             for (int v = 0; v < G.V(); v++)
 25             {
 26                 if (G.outdegree(v) > G.indegree(v))                 // 计算 deficit 不能直接加总出度和入度的差
 27                 {                                                   // 因为平行边不影响 G.outdegree(v) - G.indegree(v)，但会导致不存在欧拉路径
 28                     deficit += (G.outdegree(v) - G.indegree(v));
 29                     s = v;
 30                 }
 31             }
 32             if (deficit > 1)                                        // 差大于 1 则不存在欧拉路径
 33                 return;
 34         }
 35         path = new Stack<Integer>();
 36         Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()];
 37         for (int v = 0; v < G.V(); v++)
 38             adj[v] = G.adj(v).iterator();
 39         Stack<Integer> stack = new Stack<Integer>();
 40         for (stack.push(s); !stack.isEmpty(); )
 41         {
 42             int v = stack.pop();
 43             for (; adj[v].hasNext(); v = adj[v].next())
 44                 stack.push(v);
 45             path.push(v);
 46         }
 47         if (path.size() != G.E() + 1)
 48             path = null;
 49     }
 50 
 51     public Iterable<Integer> path()
 52     {
 53         return path;
 54     }
 55 
 56     public boolean hasEulerianPath()
 57     {
 58         return path != null;
 59     }
 60 
 61     private static int nonIsolatedVertex(Digraph G)
 62     {
 63         for (int v = 0; v < G.V(); v++)
 64         {
 65             if (G.outdegree(v) > 0)
 66                 return v;
 67         }
 68         return -1;
 69     }
 70 
 71     private static boolean satisfiesNecessaryAndSufficientConditions(Digraph G)
 72     {
 73         if (G.E() == 0)
 74             return true;
 75         int deficit = 0;
 76         for (int v = 0; v < G.V(); v++)
 77         {
 78             if (G.outdegree(v) > G.indegree(v))
 79                 deficit += (G.outdegree(v) - G.indegree(v));
 80         }
 81         if (deficit > 1)
 82             return false;
 83         Graph H = new Graph(G.V());
 84         for (int v = 0; v < G.V(); v++)
 85         {
 86             for (int w : G.adj(v))
 87                 H.addEdge(v, w);
 88         }
 89         BreadthFirstPaths bfs = new BreadthFirstPaths(H, nonIsolatedVertex(G));
 90         for (int v = 0; v < G.V(); v++)
 91         {
 92             if (H.degree(v) > 0 && !bfs.hasPathTo(v))
 93                 return false;
 94         }
 95         return true;
 96     }
 97 
 98     private static void unitTest(Digraph G, String description)
 99     {
100         System.out.printf("
%s--------------------------------
", description);
101         StdOut.print(G);
102         class01 euler = new class01(G);
103         System.out.printf("Eulerian path: ");
104         if (euler.hasEulerianPath())
105         {
106             for (int v : euler.path())
107                 System.out.printf(" %d", v);
108         }
109         StdOut.println();
110     }
111 
112     public static void main(String[] args)
113     {
114         int V = Integer.parseInt(args[0]);
115         int E = Integer.parseInt(args[1]);
116 
117         Digraph G1 = DigraphGenerator.eulerianCycle(V, E);
118         unitTest(G1, "Eulerian cycle");
119 
120         Digraph G2 = DigraphGenerator.eulerianPath(V, E);
121         unitTest(G2, "Eulerian path");
122 
123         Digraph G3 = new Digraph(G2);
124         G3.addEdge(StdRandom.uniform(V), StdRandom.uniform(V));
125         unitTest(G3, "one random edge added to Eulerian path");
126 
127         Digraph G4 = new Digraph(V);
128         int v4 = StdRandom.uniform(V);
129         G4.addEdge(v4, v4);
130         unitTest(G4, "single self loop");
131 
132         Digraph G5 = new Digraph(V);
133         G5.addEdge(StdRandom.uniform(V), StdRandom.uniform(V));
134         unitTest(G5, "single edge");
135 
136         Digraph G6 = new Digraph(V);
137         unitTest(G6, "empty digraph");
138 
139         Digraph G7 = DigraphGenerator.simple(V, E);
140         unitTest(G7, "simple digraph");
141     }
142 }