算法学习-欧拉路径与欧拉回路（JAVA实现）

本文最后更新于：April 7, 2022 am

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

预知

  1. 欧拉回路：若图G中存在这样一条路径， 使得它恰好通过G中每条边一次，则称该路径为欧拉路径（欧拉通路）。若该路径是一个环路, 则称为欧拉(Euler)回路。

  • 具有欧拉回路的图称称为欧拉图。

  • 具有欧拉路径但不具有欧拉回路的图称为半欧拉图。

定理和推论

无向图

    1. 一个无向图G存在欧拉路径当且仅当无向图G是连通图，且该图中有两个奇度顶点（度数为奇数）或者无奇度顶点。
    1. 当无向图G是仅有两个奇度顶点的连通图时，G的欧拉路径必定以这两个奇度顶点为端点。
    1. 一个无向图G存在欧拉回路当且仅当无向图G连通不存在奇度顶点。（当G是无奇度顶点的连通图时，G必有欧拉回路。）

有向图

  1. 一个有向图G存在欧拉路径当且仅当G的基图连通，且满足以下两个条件之一 :
    • 所有顶点的入度和出度相等;（路径为环）
    • 除两个顶点外，其余顶点的出度与入度都相等。且这两个顶点有一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1。其他顶点的入度和出度相等。（路径为线）
  1. 当有向图G包含两个入度和出度不相同的顶点且有欧拉路径时，欧拉路径必定以这两个入度出度不相同的顶点为端点，且必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为终点。
  1. 一个有向图G存在欧拉回路当且仅当图G是连通的有向图，且所有顶点的入度和出度相等。

欧拉通路、回路存在的判断

判断欧拉通路是否存在的方法

有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。

无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

判断欧拉回路是否存在的方法

有向图：图连通，所有的顶点出度=入度。

无向图：图连通，所有顶点都是偶数度。（G为欧拉图（存在欧拉回路）的充分必要条件是G为无奇度结点的连通图。）

欧拉回路的应用

哥尼斯堡七桥问题、一笔画问题、旋转鼓轮的设计。

代码实现

无向图

邻接矩阵存图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.io.*;
import java.math.BigInteger;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 2000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;
    public static int[][] grap = new int[maxd][maxd]; //存储关系
    public static boolean[][] vis = new boolean[maxd][maxd]; //是否访问过
    public static int n; //n个点
    public static int cnt=0; //找到的边的条数

    public static void euler(int u){
        for(int i=1;i<=n;++i){
            if(grap[u][i]>0 && !vis[u][i]){
                vis[u][i]=vis[i][u]=true;
                euler(i);
                System.out.println(u+"->"+i);
                cnt++;
            }
        }
    }

    public static void main(String[] args) throws Exception {

        n = nextInt();
        int m = nextInt(); //m条边
        for(int i=1;i<=m;++i){
            int a = nextInt();
            int b = nextInt();
            grap[a][b]++;
            grap[b][a]++;
        }
        euler(1);
        System.out.println("长度为："+cnt);

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

输入输出：

1
2
3
4
5
6
7
8
9
10
11
//输入
3 3
1 2
2 3
1 3
    
//输出    
3->1
2->3
1->2
长度为：3

有向图

邻接矩阵存图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.io.*;
import java.math.BigInteger;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 2000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;
    public static int[][] grap = new int[maxd][maxd];
    public static boolean[][] vis = new boolean[maxd][maxd];
    public static int n;
    public static int cnt=0;

    public static void euler(int u){
        for(int i=1;i<=n;++i){
            if(grap[u][i]>0 && !vis[u][i]){
                vis[u][i]=true;
                euler(i);
                System.out.println(u+"->"+i);
                cnt++;
            }
        }
    }

    public static void main(String[] args) throws Exception {

        n = nextInt();
        int m = nextInt();
        for(int i=1;i<=m;++i){
            int a = nextInt();
            int b = nextInt();
            grap[a][b]++;
        }
        euler(1);
        System.out.println("长度为："+cnt);

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

输出输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//输入
5 6
2 3
2 5
3 4
1 2
4 2
5 1

//输出    
5->1
2->5
4->2
3->4
2->3
1->2
长度为：6

练习题目

洛谷 P7771 欧拉路径 ：判定 + 寻找欧拉路径

洛谷 P1341 无序字母对：判定 + 寻找欧拉路径

洛谷 P2731 骑马修栅栏：寻找欧拉路径

洛谷 P1127 词链：判定 + 寻找欧拉路径