欧拉路径
发布于2021-02-01
上次编辑2021-04-19
简介
在给定的 连通图 中，如果某条路径经过每条边 恰好一次，则该路径称为 欧拉路径（Eulerian path/Eulerian trail）。如果路径的起点与终点相同，则称为 欧拉回路（Eulerian cycle/Eulerian circuit）。直观的讲，欧拉回路 可以从 任意一点 开始 一笔画完 整个图，而 欧拉路径 必须从 某个点 开始才能 一笔画完 整个图。
具有欧拉回路的图叫做 欧拉图（Eulerian graph），而具有欧拉路径不具有欧拉回路的图叫做 半欧拉图（semi-Eulerian）。
存在性判断
在 无向图 （连通图）中：
- 如果所有点的 度数 都为 偶数，则从任意点出发，最终一定会回到起点（欧拉回路）。
- 如果 有且仅有两个点 的度数为 奇数，则必须从其中一个奇数度数的点出发，然后回到另一个奇数度数的点。
- 否则，不存在欧拉路径。
在 有向图 （强连通）中：
- 如果所有点的 出度 与 入度 相等，则存在欧拉回路。
- 如果只存在一个点的 出度 比 入度 大 \(1\) （起点），和一个点的 入度 比 出度 大 \(1\)，而其他点的 出度 与 入度 相等，则存在欧拉路径。
- 否则，不存在欧拉路径。
寻找欧拉路径
可以使用 Fleury 算法和 Hierholzer 算法来寻找欧拉路径，但是 Fleury 算法的时间复杂度为 \(\mathcal{O}(|E|^2)\)，而 Hierholzer 算法的时间复杂度为 \(\mathcal{O}(|E|)\)。
Hierholzer 算法
从某个点开始，进行深度优先搜索，搜索到下一个点时，将该点与下一个点相连的边删去，因为每条边只遍历一次。
如果到达某个点时，无法继续向下搜索，则说明这个点是当前搜索的 终点，因为只有终点的 入度 大于 出度。换句话说，一个点成为当前搜索的终点的条件是：它没有指出的边。或者说，只有当一个点的所有指出的边遍历完（删除）后，该点才能成为终点。
然后将这个点加入到欧拉路径中。
重复上述步骤直到没有边存在。
但是注意这样得到的欧拉路径是与开始的点相反的路径。
332. 重新安排行程
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj = defaultdict(list)
for u, v in tickets:
adj[u].append(v)
for u in adj:
adj[u].sort(reverse=True)
ans = []
def dfs(u: str) -> None:
while adj[u]:
v = adj[u].pop()
dfs(v)
ans.append(u)
dfs("JFK")
return ans[::-1]
|
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 | class Solution {
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
unordered_map<string, vector<string>> adj;
for (auto &p : tickets) {
adj[p[0]].emplace_back(p[1]);
}
for (auto &[_, v] : adj) {
sort(v.begin(), v.end(), greater<>());
}
vector<string> ans;
function<void(string)> dfs;
dfs = [&dfs, &adj, &ans] (string u) {
while (!adj[u].empty()) {
auto v = adj[u].back(); adj[u].pop_back();
dfs(v);
}
ans.emplace_back(u);
};
dfs("JFK");
reverse(ans.begin(), ans.end());
return ans;
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
adj = defaultdict(list)
for u, v in tickets:
adj[u].append(v)
for u in adj:
adj[u].sort(reverse=True)
cur_path, euler_path = [], []
cur_path.append("JFK")
while cur_path:
cur_v = cur_path[-1]
if adj[cur_v]:
cur_path.append(adj[cur_v].pop())
else:
euler_path.append(cur_v)
cur_path.pop()
return euler_path[::-1]
|
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 | class Solution {
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
unordered_map<string, vector<string>> adj;
for (auto &p : tickets) {
adj[p[0]].emplace_back(p[1]);
}
for (auto &[_, v] : adj) {
sort(v.begin(), v.end(), greater<>());
}
stack<string> cur_path;
vector<string> euler_path;
cur_path.emplace("JFK");
while (!cur_path.empty()) {
auto cur_v = cur_path.top();
if (!adj[cur_v].empty()) {
auto next_v = adj[cur_v].back();
adj[cur_v].pop_back();
cur_path.emplace(next_v);
} else {
euler_path.emplace_back(cur_v);
cur_path.pop();
}
}
reverse(euler_path.begin(), euler_path.end());
return euler_path;
}
};
|
例题