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

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

● 无向图中寻找欧拉环

  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)                 // 至少有 1 条边
 41             return;
 42         for (int v = 0; v < G.V(); v++) // 欧拉环要求每个顶点的度均为偶数
 43         {
 44             if (G.degree(v) % 2 != 0)
 45                 return;
 46         }
 47         Queue<Edge>[] adj = (Queue<Edge>[]) new Queue[G.V()];   // 把邻接表每个链表转化为一个队列，以便遍历（其实可以不要？）
 48         for (int v = 0; v < G.V(); v++)
 49             adj[v] = new Queue<Edge>();
 50         for (int v = 0; v < G.V(); v++)
 51         {
 52             boolean selfEdge = false;           // 用于判断奇偶
 53             for (int w : G.adj(v))
 54             {
 55                 if (v == w)
 56                 {
 57                     if (!selfEdge)              // 考虑某个顶点的链表出现 2k 次自己，实际只有 k 条自边，即 k 个自环
 58                     {
 59                         Edge e = new Edge(v, w);
 60                         adj[v].enqueue(e);
 61                         adj[w].enqueue(e);
 62                     }
 63                     selfEdge = !selfEdge;
 64                 }
 65                 else if (v < w)                 // 控制索引只添加向后顶点的边，防止重复计数
 66                 {
 67                     Edge e = new Edge(v, w);
 68                     adj[v].enqueue(e);
 69                     adj[w].enqueue(e);
 70                 }
 71             }
 72         }
 73         Stack<Integer> stack = new Stack<Integer>();            // 用栈保存遍历顺序，也即欧拉环中顶点顺序
 74         stack.push(nonIsolatedVertex(G));                       // 第一个非孤立点压栈
 75         for (cycle = new Stack<Integer>(); !stack.isEmpty();)
 76         {
 77             int v = stack.pop();
 78             for (; !adj[v].isEmpty();)                          // 深度优先遍历
 79             {
 80                 Edge edge = adj[v].dequeue();
 81                 if (edge.isUsed)
 82                     continue;
 83                 edge.isUsed = true;     // 从 adj[v] 处改 edge(v,w) 则 adj[w] 相应顶点也变化，保证每条边只修改一次，防止回头路
 84                 stack.push(v);
 85                 v = edge.other(v);
 86             }
 87             cycle.push(v);              // 遍历完成，把终点入栈
 88         }
 89         if (cycle.size() != G.E() + 1)  // 存储了遍历顺序，起点终点记两次，所以比边数多 1
 90             cycle = null;        
 91     }
 92 
 93     public Iterable<Integer> cycle()
 94     {
 95         return cycle;
 96     }
 97 
 98     public boolean hasEulerianCycle()
 99     {
100         return cycle != null;
101     }
102 
103     private static int nonIsolatedVertex(Graph G)   // 寻找图上的第一个非独立点，也即度数大于 0 的点
104     {
105         for (int v = 0; v < G.V(); v++)
106         {
107             if (G.degree(v) > 0)
108                 return v;
109         }
110         return -1;
111     }
112 
113     private static boolean satisfiesNecessaryAndSufficientConditions(Graph G)   // 用欧拉环的充要条件进行判定
114     {
115         if (G.E() == 0)                             // 至少有一条边
116             return false;
117         for (int v = 0; v < G.V(); v++)             // 每个顶点的度是偶数
118         {
119             if (G.degree(v) % 2 != 0)
120                 return false;
121         }
122         BreadthFirstPaths bfs = new BreadthFirstPaths(G, nonIsolatedVertex(G)); // 图是连通的
123         for (int v = 0; v < G.V(); v++)
124         {
125             if (G.degree(v) > 0 && !bfs.hasPathTo(v))
126                 return false;
127         }
128         return true;
129     }  
130 
131     private static void unitTest(Graph G, String description)
132     {
133         System.out.printf("
%s--------------------------------
", description);
134         StdOut.print(G);
135         class01 euler = new class01(G);
136         System.out.printf("Eulerian cycle: ");
137         if (euler.hasEulerianCycle())
138         {
139             for (int v : euler.cycle())
140                 System.out.printf(" %d", v);
141         }
142         System.out.println();
143     }
144 
145     public static void main(String[] args)
146     {
147         int V = Integer.parseInt(args[0]);
148         int E = Integer.parseInt(args[1]);
149 
150         Graph G1 = GraphGenerator.eulerianCycle(V, E);
151         unitTest(G1, "Eulerian cycle");
152 
153         Graph G2 = GraphGenerator.eulerianPath(V, E);
154         unitTest(G2, "Eulerian path");
155 
156         Graph G3 = new Graph(V);
157         unitTest(G3, "Empty graph");
158 
159         Graph G4 = new Graph(V);
160         int v4 = StdRandom.uniform(V);
161         G4.addEdge(v4, v4);
162         unitTest(G4, "Single self loop");
163 
164         Graph H1 = GraphGenerator.eulerianCycle(V / 2, E / 2);          // 把两个欧拉环连在一起
165         Graph H2 = GraphGenerator.eulerianCycle(V - V / 2, E - E / 2);
166         int[] perm = new int[V];
167         for (int i = 0; i < V; i++)
168             perm[i] = i;
169         StdRandom.shuffle(perm);
170         Graph G5 = new Graph(V);
171         for (int v = 0; v < H1.V(); v++)
172         {
173             for (int w : H1.adj(v))
174                 G5.addEdge(perm[v], perm[w]);
175         }
176         for (int v = 0; v < H2.V(); v++)
177         {
178             for (int w : H2.adj(v))
179                 G5.addEdge(perm[V / 2 + v], perm[V / 2 + w]);
180         }
181         unitTest(G5, "Union of two disjoint cycles");
182 
183         Graph G6 = GraphGenerator.simple(V, E);
184         unitTest(G6, "Random simple graph");
185     }
186 }

● 有向图中寻找欧拉环，只注释了与上面不同的地方

  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> cycle = new Stack<Integer>();
 15 
 16     public class01(Digraph G)
 17     {
 18         if (G.E() == 0)                 // 至少有一条边
 19             return;
 20         for (int v = 0; v < G.V(); v++) // 要求每个店的入度等于出度（否则至多为欧拉环路径，不能是环）
 21         {
 22             if (G.outdegree(v) != G.indegree(v))
 23                 return;
 24         }
 25         Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()];    // 使用迭代器而不是队列来存储
 26         for (int v = 0; v < G.V(); v++)
 27             adj[v] = G.adj(v).iterator();
 28         Stack<Integer> stack = new Stack<Integer>();        
 29         for (stack.push(nonIsolatedVertex(G)); !stack.isEmpty();)
 30         {
 31             int v = stack.pop();
 32             for (; adj[v].hasNext(); v = adj[v].next())
 33                 stack.push(v);
 34             cycle.push(v);
 35         }
 36         if (cycle.size() != G.E() + 1)
 37             cycle = null;
 38     }
 39 
 40     public Iterable<Integer> cycle()
 41     {
 42         return cycle;
 43     }
 44 
 45     public boolean hasEulerianCycle()
 46     {
 47         return cycle != null;
 48     }
 49 
 50     private static int nonIsolatedVertex(Digraph G)
 51     {
 52         for (int v = 0; v < G.V(); v++)
 53         {
 54             if (G.outdegree(v) > 0)
 55                 return v;
 56         }
 57         return -1;
 58     }
 59 
 60     private static boolean satisfiesNecessaryAndSufficientConditions(Digraph G) // 用欧拉环的充要条件进行判定
 61     {
 62         if (G.E() == 0)                 // 至少有 1 条边
 63             return false;
 64         for (int v = 0; v < G.V(); v++) // 每个顶点的入度等于出度
 65         {
 66             if (G.outdegree(v) != G.indegree(v))
 67                 return false;
 68         }
 69         Graph H = new Graph(G.V());     // 把图做成无向的，判断所有顶点连通
 70         for (int v = 0; v < G.V(); v++)
 71         {
 72             for (int w : G.adj(v))
 73                 H.addEdge(v, w);
 74         }
 75         BreadthFirstPaths bfs = new BreadthFirstPaths(H, nonIsolatedVertex(G));
 76         for (int v = 0; v < G.V(); v++)
 77         {
 78             if (H.degree(v) > 0 && !bfs.hasPathTo(v))
 79                 return false;
 80         }
 81         return true;
 82     }
 83 
 84     private static void unitTest(Digraph G, String description)
 85     {
 86         System.out.printf("
%s--------------------------------
", description);
 87         StdOut.print(G);
 88         class01 euler = new class01(G);
 89         System.out.printf("Eulerian cycle: ");
 90         if (euler.hasEulerianCycle())
 91         {
 92             for (int v : euler.cycle())
 93                 System.out.printf(" %d", v);
 94         }
 95         StdOut.println();
 96     }
 97 
 98     public static void main(String[] args)
 99     {
100         int V = Integer.parseInt(args[0]);
101         int E = Integer.parseInt(args[1]);
102 
103         Digraph G1 = DigraphGenerator.eulerianCycle(V, E);
104         unitTest(G1, "Eulerian cycle");
105 
106         Digraph G2 = DigraphGenerator.eulerianPath(V, E);
107         unitTest(G2, "Eulerian path");
108 
109         Digraph G3 = new Digraph(V);
110         unitTest(G3, "Empty digraph");
111 
112         Digraph G4 = new Digraph(V);
113         int v4 = StdRandom.uniform(V);
114         G4.addEdge(v4, v4);
115         unitTest(G4, "single self loop");
116 
117         Digraph H1 = DigraphGenerator.eulerianCycle(V / 2, E / 2);
118         Digraph H2 = DigraphGenerator.eulerianCycle(V - V / 2, E - E / 2);
119         int[] perm = new int[V];
120         for (int i = 0; i < V; i++)
121             perm[i] = i;
122         StdRandom.shuffle(perm);
123         Digraph G5 = new Digraph(V);
124         for (int v = 0; v < H1.V(); v++)
125         {
126             for (int w : H1.adj(v))
127                 G5.addEdge(perm[v], perm[w]);
128         }
129         for (int v = 0; v < H2.V(); v++)
130         {
131             for (int w : H2.adj(v))
132                 G5.addEdge(perm[V / 2 + v], perm[V / 2 + w]);
133         }
134         unitTest(G5, "Union of two disjoint cycles");
135 
136         Digraph G6 = DigraphGenerator.simple(V, E);
137         unitTest(G6, "Simple digraph");
138         /*
139         Digraph G7 = new Digraph(new In("eulerianD.txt"));
140         unitTest(G7, "4-vertex Eulerian digraph from file");
141         */
142     }
143 }