Euler Circuit & Euler Trail

Trail: a walk that does not repeat any edges.
Closed Trail(Circuit): a trail that begins and ends at the same vertex.
Eulerian Circuit: a circuit that includes every edge of the graph.
Eulerian Trail: a trail that includes every edge of the graph.

在无向图中，图 $G$ 有欧拉回路当且仅当每个点的度数为偶数。
在有向图中，图 $G$ 有欧拉回路当且仅当每个点的入度和出度相同。
在无向图中，图 $G$ 有欧拉路径(非欧拉回路)当且仅当只有两个点的度数为奇数，其余都是偶数。
在有向图中，图 $G$ 有欧拉路径(非欧拉回路)当且仅当只有两个点的入度和出度不同，且其中一个点的“入度 $-$ 出度=1”，另一个点的“出度 $-$ 入度=1”。

输出欧拉回路和欧拉路径的常用算法是 Hierholzer's Algorithm 和 Fleury's Algorithm，复杂度分别为 $O(E)$ 和 $O(E^2)$。

Hierholzer's Algorithm的正确性：因为一个具有欧拉回路的图G能够拆分成多个边不相交的环，因此这个算法正确。

 1 Find a circuit called $R_1$
 2 mark all edges of $R_1$
 3 i=1;
 4 while(true)
 5 {
 6     if $R_1$ contains all edges of G, then return;
 7     else
 8     {
 9         let $v_i$ be a vertex on $R_i$ that is incident with unmarked edge;
10         build a circuit $Q_i$ from $v_i$;
11         mark all edges of $Q_i$;
12         $R_{i+1} = R_i \cup Q_i$;
13         i++;
14     }
15 }
Hierholzer's Algorithm的伪代码
  1 import java.util.LinkedList;
  2 import java.util.List;
  3 import java.util.Scanner;
  4 
  5 public class EularTrail {
  6     int n;
  7     int m;
  8     int head[];
  9     int edge[][];
 10     int next[];
 11     int visited[];
 12     int ee = 0;    
 13     int indegree[];
 14     int outdegree[];
 15     LinkedList<Pair> queue = new LinkedList<Pair>();
 16     List<Integer> tmpList = new LinkedList<Integer>();
 17     List<Integer> resultList = new LinkedList<Integer>();
 18     
 19     int index[][];
 20     int start = 1;
 21     int end = 0;
 22     public boolean eularTrail(){
 23         calculateDegree();
 24         boolean isEularCircuit = hasEularCircuit();
 25         boolean isEularTrail = hasEularTrail();
 26         if(isEularTrail || isEularCircuit){
 27             tmpList.add(start);
 28             findCycle(start, 0);
 29             while(!queue.isEmpty()){
 30                 Pair u = queue.removeLast();    //注意这里只能用removeLast而不能用removeFirst
 31                 findCycle(u.vertex,u.pos);
 32             }
 33             printEular();
 34             return true;
 35         }
 36         else return false;
 37     }
 38     
 39     /**
 40      * 判定输入的路径是否是欧拉路径
 41      * @return
 42      */
 43     public boolean checkEularTrail(){
 44         System.out.println("###################");
 45         System.out.println("#Check Eular Trail#");
 46         System.out.println("###################");
 47         System.out.println("Input path:");
 48         Scanner in = new Scanner(System.in);
 49         boolean[] pathVisited = new boolean[m];
 50         for(int i=0;i<m;i++){
 51             pathVisited[i] = false;
 52         }
 53         int[] sequence = new int[m+1];
 54         for(int i=0;i<m+1;i++){
 55             sequence[i] = in.nextInt();
 56         }
 57         for(int i=0;i<m;i++){
 58             int begin = sequence[i];
 59             int end = sequence[i+1];
 60             pathVisited[index[begin][end]]=true;
 61         }
 62         for(int i=0;i<m;i++){
 63             if(pathVisited[i]==false){
 64                 System.out.println("\nNot a Eular Trail!");
 65                 return false;
 66             }
 67         }
 68         System.out.println("\nIs a Eular Trail!");
 69         return true;
 70     }
 71     
 72     private void calculateDegree() {
 73         for(int i=1;i<=n;i++){
 74             for(int j=head[i];j!=-1;j=next[j]){
 75                 outdegree[i]++;
 76                 indegree[edge[j][1]]++;
 77             }
 78         }
 79     }
 80     private void printEular(){
 81         for(int i=0;i<resultList.size();i++){
 82             System.out.println(resultList.get(i));
 83         }
 84     }
 85     private boolean hasEularTrail() {
 86         int start_count = 0;
 87         int end_count = 0;
 88         for(int i=1;i<=n;i++){
 89             if(indegree[i]!=outdegree[i]){
 90                 if((indegree[i]-outdegree[i])!=1 && (indegree[i]-outdegree[i])!=-1){
 91                     return false;
 92                 }
 93                 else if((indegree[i]-outdegree[i])==1){
 94                     end = i;
 95                     end_count++;
 96                 }
 97                 else if((indegree[i]-outdegree[i])==-1){
 98                     start = i;
 99                     start_count++;
100                 }
101             }
102         }
103         if(start_count!=1 || end_count!=1) return false;
104         return true;
105     }
106     
107     private void findCycle(int i,int begin) {
108         DFS(i,i,begin);
109         resultList.addAll(begin,tmpList);
110         tmpList.clear();
111     }
112     private boolean DFS(int source,int i,int begin){
113         if(outdegree[i]==0){
114             return true;
115         }
116         for(int j=head[i];j!=-1;j=next[j]){
117             int end = edge[j][1];
118             
119             if(visited[j]==0){
120                 visited[j] = 1;
121                 outdegree[i]--;
122                 if(outdegree[i]>0&&!queue.contains(i)){
123                     queue.add(new Pair(i,begin+tmpList.size()));
124                 }
125                 tmpList.add(end);
126                 if(end==source){
127                     if(outdegree[end]>0&&!queue.contains(end)){
128                         queue.add(new Pair(end,begin+tmpList.size()));
129                     }
130                     return false;
131                 }
132                 boolean flag =  DFS(source,edge[j][1],begin);
133                 if(flag==false){
134                     return false;
135                 }
136             }
137         }
138         return true;
139     }
140     
141     private boolean hasEularCircuit() {
142         for(int i=1;i<=n;i++){
143             if(indegree[i]!=outdegree[i]){
144                 return false;
145             }
146         }
147         return true;
148     }
149     public void input(){
150         System.out.println("Input Graph:");
151         Scanner in = new Scanner(System.in);
152         n = in.nextInt();
153         m = in.nextInt();
154         head = new int[n+1];
155         next = new int[m];
156         edge = new int[m][2];
157         visited = new int[m];
158         indegree = new int[n+1];
159         outdegree = new int[n+1];
160         index = new int[n+1][n+1];
161         for(int i=1;i<=n;i++){
162             head[i] = -1;
163             outdegree[i] = 0;
164             indegree[i] = 0;
165         }
166         for(int i=0;i<m;i++){
167             next[i] = -1;
168             visited[i] = 0;
169         }
170         for(int i=1;i<=m;i++){
171             int begin = in.nextInt();
172             int end = in.nextInt();
173             edge[ee][0] = begin;
174             edge[ee][1] = end;
175             next[ee] = head[begin];
176             head[begin] = ee;
177             index[begin][end] = ee;
178             ee++;
179         }
180     }
181     public static void main(String[] args) {
182         EularTrail hierholzer = new EularTrail();
183         hierholzer.input();
184         hierholzer.eularTrail();
185         //boolean flag = hierholzer.checkEularTrail();
186         //System.out.println(flag);
187     }
188 }
Eular Trail的Java实现
  1 import java.util.LinkedList;
  2 import java.util.List;
  3 import java.util.Scanner;
  4 
  5 class Pair{
  6     int vertex;
  7     int pos;
  8     public Pair(int vertex,int pos){
  9         this.vertex = vertex;
 10         this.pos = pos;
 11     }
 12     @Override
 13     public String toString() {
 14         return "Pair [vertex=" + vertex + ", pos=" + pos + "]";
 15     }
 16 }
 17 public class EularCircuit {
 18     int n;
 19     int m;
 20     int head[];
 21     int edge[][];
 22     int next[];
 23     int visited[];
 24     int ee = 0;    
 25     int indegree[];
 26     int outdegree[];
 27     LinkedList<Pair> queue = new LinkedList<Pair>();
 28     List<Integer> tmpList = new LinkedList<Integer>();
 29     List<Integer> resultList = new LinkedList<Integer>();
 30     
 31     int index[][];
 32     public boolean eularCircuit(){
 33         calculateDegree();
 34         boolean isEular = hasEularCircuit();
 35         if(!isEular) return false;
 36         tmpList.add(1);
 37         findCycle(1, 0);
 38         while(!queue.isEmpty()){
 39             Pair u = queue.removeLast();    //注意这里只能用removeLast而不能用removeFirst
 40             findCycle(u.vertex,u.pos);
 41         }
 42         printEular();
 43         return true;
 44     }
 45     /**
 46      * 判定输入的路径是否是欧拉回路
 47      * @return
 48      */
 49     public boolean checkEularCircuit(){
 50         System.out.println("#####################");
 51         System.out.println("#Check Eular Circuit#");
 52         System.out.println("#####################");
 53         System.out.println("Input path:");
 54         Scanner in = new Scanner(System.in);
 55         boolean[] pathVisited = new boolean[m];
 56         for(int i=0;i<m;i++){
 57             pathVisited[i] = false;
 58         }
 59         int[] sequence = new int[m+1];
 60         for(int i=0;i<m+1;i++){
 61             sequence[i] = in.nextInt();
 62         }
 63         if(sequence[0]!=sequence[m]) {
 64             System.out.println("\nNot a Eular Circuit!");
 65             return false;
 66         }
 67         for(int i=0;i<m;i++){
 68             int begin = sequence[i];
 69             int end = sequence[i+1];
 70             pathVisited[index[begin][end]]=true;
 71         }
 72         for(int i=0;i<m;i++){
 73             if(pathVisited[i]==false){
 74                 System.out.println("\nNot a Eular Circuit!");
 75                 return false;
 76             }
 77         }
 78         System.out.println("\nIs a Eular Circuit!");
 79         return true;
 80     }
 81     public void input(){
 82         System.out.println("Input Graph:");
 83         Scanner in = new Scanner(System.in);
 84         n = in.nextInt();
 85         m = in.nextInt();
 86         head = new int[n+1];
 87         next = new int[m];
 88         edge = new int[m][2];
 89         visited = new int[m];
 90         indegree = new int[n+1];
 91         outdegree = new int[n+1];
 92         index = new int[n+1][n+1];
 93         for(int i=1;i<=n;i++){
 94             head[i] = -1;
 95             outdegree[i] = 0;
 96             indegree[i] = 0;
 97         }
 98         for(int i=0;i<m;i++){
 99             next[i] = -1;
100             visited[i] = 0;
101         }
102         for(int i=1;i<=m;i++){
103             int begin = in.nextInt();
104             int end = in.nextInt();
105             edge[ee][0] = begin;
106             edge[ee][1] = end;
107             next[ee] = head[begin];
108             head[begin] = ee;
109             index[begin][end] = ee;
110             ee++;
111         }
112     }
113 
114     private void calculateDegree() {
115         for(int i=1;i<=n;i++){
116             for(int j=head[i];j!=-1;j=next[j]){
117                 outdegree[i]++;
118                 indegree[edge[j][1]]++;
119             }
120         }
121     }
122     private boolean hasEularCircuit() {
123         for(int i=1;i<=n;i++){
124             if(indegree[i]!=outdegree[i]){
125                 return false;
126             }
127         }
128         return true;
129     }
130     /*从i开始寻找一个环，即 i->....->i */
131     private void findCycle(int i,int begin) {
132         DFS(i,i,begin);
133         resultList.addAll(begin,tmpList);
134         tmpList.clear();
135     }
136     
137     private boolean DFS(int source,int i,int begin){
138         if(outdegree[i]==0){
139             return true;
140         }
141         for(int j=head[i];j!=-1;j=next[j]){
142             int end = edge[j][1];
143             
144             if(visited[j]==0){
145                 visited[j] = 1;
146                 outdegree[i]--;
147                 if(outdegree[i]>0&&!queue.contains(i)){
148                     queue.add(new Pair(i,begin+tmpList.size()));
149                 }
150                 tmpList.add(end);
151                 if(end==source){
152                     if(outdegree[end]>0&&!queue.contains(end)){
153                         queue.add(new Pair(end,begin+tmpList.size()));
154                     }
155                     return false;
156                 }
157                 boolean flag =  DFS(source,edge[j][1],begin);
158                 if(flag==false){
159                     return false;
160                 }
161             }
162         }
163         return true;
164     }
165     /*输出欧拉回路*/
166     private void printEular(){
167         for(int i=0;i<resultList.size();i++){
168             System.out.println(resultList.get(i));
169         }
170     }
171     
172     public static void main(String[] args) {
173         EularCircuit hierholzer = new EularCircuit();
174         hierholzer.input();
175         hierholzer.eularCircuit();
176         boolean flag = hierholzer.checkEularCircuit();
177         System.out.println(flag);
178     }
179     
180 }
Eular Circuit的Java实现

其中，EularCircuit 类的功能：

  • 输入图
  • 检测给定序列是否为欧拉回路
  • 输出欧拉回路

EularTrail 类的功能：

  • 输入图
  • 检测给定序列是否为欧拉路径
  • 输出欧拉路径
16 56
1 2
2 1
1 5
5 1
2 3
3 2
2 5
5 2
2 6
6 2
3 4
4 3
3 7
7 3
3 8
8 3
4 8
8 4
5 6
6 5
5 9
9 5
6 7
7 6
6 10
10 6
7 8
8 7
7 11
11 7
8 12
12 8
9 10
10 9
9 13
13 9
9 14
14 9
10 11
11 10
10 14
14 10
11 12
12 11
11 15
15 11
12 15
15 12
12 16
16 12
13 14
14 13
14 15
15 14
15 16
16 15
Sample Input of Eular Circuit
1
5
9
14
15
16
15
14
13
14
10
14
9
13
9
10
11
15
12
16
12
15
11
12
11
10
9
5
6
10
6
7
11
7
8
12
8
7
6
5
2
6
2
5
1
2
3
8
4
8
3
7
3
4
3
2
1
Sample Output of Eular Circuit
4 5
1 4
4 3
3 2
2 1
1 3
Sample Input of Eular Trail
1
3
2
1
4
3
Sample Output of Eular Trail
作者：xiazdong
出处：http://blog.xiazdong.info
本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xiazdong/p/3098352.html