欧拉路径

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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