算法图算法

欧拉路径

字数统计: 2.5k字   |   阅读时长: 11分
, , ,

摘要: 本文介绍欧拉路径的判定定理、算法、代码模板和例题。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

欧拉(1707-1783)

1736 年欧拉解决七桥问题，从七桥问题出发，进一步可以抽象出欧拉路径的概念。欧拉七桥问题与哈密顿周游世界游戏埋下了图论诞生的种子，并在 20 世纪迅速发展，成为现在重要的数学分支。

本文我们来学习欧拉路径想的算法。首先介绍欧拉路径的一些判定定理，包括有向图欧拉路径、无向图欧拉路径、有向图欧拉回路、无向图欧拉回路。然后简要介绍寻找欧拉回路的算法，并且给出代码模板，最后我们用代码模板解决力扣上两个相关题目。

关于欧拉路径的定义和性质，可以参考文章 图论4-欧拉图,哈密顿图。

$0 判定有欧拉路径

step1: 判定连通图

step2:

  • 无向连通图有欧拉路径的充要条件：所有点度均为偶数，或者除了两个点的度为奇数，其余都为偶数。
  • 有向连通图有欧拉路径的充要条件：所有点入度和出度相等，或者除了两个点，其余的点的入度和出度相等。并且这两个点一个入度比出度大 1，另一个入度比出度小 1。

$1 判定有欧拉回路

step1: 判定连通图

step2:

  • 无向连通图是欧拉图的充要条件：所有点度均为偶数。
  • 有向连通图是欧拉图的充要条件：所有点入度和出度相等。

$2 寻找欧拉回路的算法

  1. DFS，指数级，与寻找哈密顿路的逻辑相同。

  2. Fluery 算法，$O(V+E)$，每个点遍历一遍，每走过一条边都删掉，剩下的邻边需要重新判断桥。

1
2
有多条边的时候，不走桥(贪心)
需要一边删边，一遍判断桥。
  1. Hierholzer 算法 $O(V+E)$: 本算法相当于欧拉图充要条件的构造性证明。

基于 DFS，使用栈 curPath 记录从某个起始点出发到当前点的路径，并且在 DFS 过程中记录最终的欧拉回路。DFS 过程如下： 

1
2
3
从起点出发，DFS:
    每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。
    如果没有可移动的路径，则将所在节点加入到栈中，并返回。

有向图代码(非递归) (模板)

已经判定欧拉回路存在之后，起点 root 可以随意给定。

DFS 过程中需要删除边，因此邻接表用 vector<list<int>> 维护。

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
vector<int> find_euler_cycle(vector<list<int>>& g, const int root)
{
    int n = g.size();
    vector<int> euler_cycle;
    stack<int> cur_path;
    cur_path.push(root);
    vector<bool> visited(n, false);
    while(!cur_path.empty())
    {
        int cur = cur_path.top();
        bool flag = false;
        list<int> &edges = g[cur];
        auto it = edges.begin();
        while(it != edges.end())
        {
            int son = *it;
            if(!visited[son])
            {
                cur_path.push(son);
                it = edges.erase(it); // 删边
                flag = true;
                break;
            }
        }
        if(!flag)
        {
            visited[cur] = true;
            euler_cycle.push_back(cur_path.top());
            cur_path.pop();
        }
    }
    reverse(euler_cycle.begin(), euler_cycle.end());
    return euler_cycle;
}

$3 寻找欧拉路径的算法

如果是寻找欧拉路径，调用方提供的起点不能随意提供了。

需要先用判定定理保证该无向图或有向图是连通的且存在欧拉路径，并且需要判定存在的从起点 root 出发确实有一条欧拉路径。

有向图代码(非递归) (模板)

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
vector<int> find_euler_path(vector<list<int>>& g, const int root)
{
    // 调用方保证从 root 出发存在欧拉路径，否则返回结果错误
    int n = g.size();
    vector<int> euler_path;
    stack<int> cur_path;
    cur_path.push(root);
    vector<bool> visited(n, false);
    while(!cur_path.empty())
    {
        int cur = cur_path.top();
        bool flag = false;
        list<int> &edges = g[cur];
        auto it = edges.begin();
        while(it != edges.end())
        {
            int son = *it;
            if(!visited[son])
            {
                cur_path.push(son);
                it = edges.erase(it); // 删边
                flag = true;
                break;
            }
        }
        if(!flag)
        {
            visited[cur] = true;
            euler_path.push_back(cur_path.top());
            cur_path.pop();
        }
    }
    reverse(euler_path.begin(), euler_path.end());
    return euler_path;
}

$4 题目

332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

提示：

1
2
3
4
5
6
1 <= tickets.length <= 300
tickets[i].length == 2
from_i.length == 3
toi.length == 3
from_i 和 to_i 由大写英文字母组成
from_i != to_i

示例 1：
输入：tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
输出：[“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]

示例 2：
输入：tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
输出：[“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
解释：另一种有效的行程是 [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”] ，但是它字典排序更大更靠后。

算法：欧拉路径

本题直接寻找欧拉路径即可：

1
2
3
首先判断图中有欧拉路径(本题不用判断)。
首先找到奇度点(本题已经给出)。
然后执行与寻找欧拉回路相同的逻辑。

代码 (C++)

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
struct Cmp
{
    vector<string> names;
    Cmp(const vector<string>& names):names(names){}
    bool operator()(const int& node1, const int& node2) const
    {
        return names[node1] < names[node2];
    }
};

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        int id = 0;
        unordered_map<string, int> mapping; // str -> idx
        for(const vector<string>& edge: tickets)
        {
            if(mapping.count(edge[0]) == 0)
                mapping[edge[0]] = id++;
            if(mapping.count(edge[1]) == 0)
                mapping[edge[1]] = id++;
        }
        int n = mapping.size();
        vector<string> names(n);
        for(const auto &item: mapping)
            names[item.second] = item.first;
        vector<list<int>> g(n);
        for(const vector<string>& edge: tickets)
            g[mapping[edge[0]]].push_back(mapping[edge[1]]);
        Cmp cmp(names);
        for(list<int> &edges: g)
            edges.sort(cmp);
        int root = mapping["JFK"];
        vector<int> euler_path = find_euler_path(g, root);
        vector<string> result;
        for(int i: euler_path)
            result.push_back(names[i]);
        return result;
    }

private:
    vector<int> find_euler_path(vector<list<int>>& g, const int root)
    {
        // 调用方保证从 root 出发存在欧拉路径，否则返回结果错误
        int n = g.size();
        vector<int> euler_path;
        stack<int> cur_path;
        cur_path.push(root);
        vector<bool> visited(n, false);
        while(!cur_path.empty())
        {
            int cur = cur_path.top();
            bool flag = false;
            list<int> &edges = g[cur];
            auto it = edges.begin();
            while(it != edges.end())
            {
                int son = *it;
                if(!visited[son])
                {
                    cur_path.push(son);
                    it = edges.erase(it); // 删边
                    flag = true;
                    break;
                }
            }
            if(!flag)
            {
                visited[cur] = true;
                euler_path.push_back(cur_path.top());
                cur_path.pop();
            }
        }
        reverse(euler_path.begin(), euler_path.end());
        return euler_path;
    }
};

753. 破解保险箱

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, …, k-1 中的一个 。

你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。

举个例子，假设密码是 “345”，你可以输入 “012345” 来打开它，只是你输入了 6 个字符.

请返回一个能打开保险箱的最短字符串。

提示：

1
2
3
n 的范围是 [1, 4]。
k 的范围是 [1, 10]。
k^n 最大可能为 4096。

示例1:
输入: n = 1, k = 2
输出: “01”
说明: “10”也可以打开保险箱。

示例2:
输入: n = 2, k = 2
输出: “00110”
说明: “01100”, “10011”, “11001” 也能打开保险箱。

算法：欧拉路径

本题并没有显式给出关于图的描述，因此需要建图的过程，这个过程在实际问题中很关键，决定了能不能顺利解决问题。

本题在正确建图后，用欧拉路径算法解决问题就比较简单了，见图过程如下：

将所有的 $n−1$ 位数作为节点，共有 $k^{n-1}$ 个节点，每个节点有 k 条入边和出边。

如果当前节点对应的数为 $a_1 a_2 \cdots a_{n-1}$，那么它的第 x 条出边就连向数 $a_2 \cdots a_{n-1} x$ 对应的节点。

这样从一个节点顺着第 x 条边走到另一个节点，就相当于输入了数字 x。

代码 (C++)

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
88
89
90
91
92
93
94
95
96
97
class Solution {
public:
    string crackSafe(int n, int k) {
        // k in [1..10]
        // n in [1..4]
        if(n == 1)
        {
            string result = "";
            for(int i = 0; i < k; ++i)
                result += '0' + i;
            return result;
        }
        items = vector<string>(pow(k, n - 1));
        mapping = unordered_map<string, int>();
        string item;
        int total = 0;
        dfs(n - 1, k, 0, item, total);
        vector<list<int>> g(total);
        build(g, k);
        vector<int> euler_path = find_euler_path(g, 0);
        string result = items[0];
        for(int i = 1; i < (int)euler_path.size(); ++i)
            result += items[euler_path[i]].back();
        return result;
    }

private:
    vector<string> items;
    unordered_map<string, int> mapping;

    vector<int> find_euler_path(vector<list<int>>& g, const int root)
    {
        // 调用方保证从 root 出发存在欧拉路径，否则返回结果错误
        int n = g.size();
        vector<int> euler_path;
        stack<int> cur_path;
        cur_path.push(root);
        vector<bool> visited(n, false);
        while(!cur_path.empty())
        {
            int cur = cur_path.top();
            bool flag = false;
            list<int> &edges = g[cur];
            auto it = edges.begin();
            while(it != edges.end())
            {
                int son = *it;
                if(!visited[son])
                {
                    cur_path.push(son);
                    it = edges.erase(it); // 删边
                    flag = true;
                    break;
                }
            }
            if(!flag)
            {
                visited[cur] = true;
                euler_path.push_back(cur_path.top());
                cur_path.pop();
            }
        }
        reverse(euler_path.begin(), euler_path.end());
        return euler_path;
    }

    void build(vector<list<int>>& g, const int k)
    {
        for(const auto &item: mapping)
        {
            const string &cur = item.first;
            for(int i = 0; i < k; ++i)
            {
                string son = cur.substr(1);
                son += '0' + i;
                g[mapping[cur]].push_back(mapping[son]);
            }
        }
    }

    void dfs(const int n, const int k, int pos, string& item, int& total)
    {
        if(pos == n)
        {
            mapping[item] = total;
            items[total] = item;
            ++total;
            return;
        }
        for(int i = 0; i < k; ++i)
        {
            item.push_back('0' + i);
            dfs(n, k, pos + 1, item, total);
            item.pop_back();
        }
    }
};
Share