欧拉通路(路径): 一条经过了图中所有边的路径， 且每条边仅经过一次。
欧拉回路: 起点和终点相同的欧拉通路。 欧拉图: 存在欧拉回路的图 半欧拉图:
不存在欧拉回路， 但存在欧拉通路的图
之所以以欧拉的名字命名，
是因为欧拉解决了与此紧密相关的一笔画问题，
即在不重复、折返的情况下遍历一张无向图。
欧拉图示例
判别欧拉图
欧拉图的判断可以使用欧拉提出的“一笔画定理”。
连通的无向图有欧拉路径的充要条件是：中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2。
连通的无向图是欧拉图（存在欧拉回路）的充要条件是：中每个顶点的度都是偶数。
证明可见:一笔画问题 -
维基百科
例题——欧拉路径
判断一无向图是欧拉图、半欧拉图还是非欧拉图
输入格式
第一行包含两个整数 N 和 M，表示无向图的点和边的数量。
接下来 M 行，每行包含两个整数 a,b，表示点 a 和 b 之间存在一条边。
所有点的编号从 1∼N。
输出格式
输出对该图的判断，Eulerian（欧拉图），Semi-Eulerian（半欧拉图），Non-Eulerian（非欧拉图）。
行尾不得有多余空格。
代码实现
- 使用并查集判断图是否连通
- 构造顶点的度数组， 用于判断欧拉图
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 510;
int p[N], d[N];
int n, m;
int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
bool isConnected() {
for (int i = 2; i <= n; i ++) {
if (find(i) != find(1)) return false;
}
return true;
}
bool hasEulerianPath() {
int odd = 0;
for (int i = 1; i <= n && odd <= 2; i ++) {
if (d[i] & 1) odd ++;
}
return odd == 0 || odd == 2;
}
bool hasEulerianCircuit() {
for (int i = 1; i <= n; i ++) {
if (d[i] & 1) return false;
}
return true;
}
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i ++) p[i] = i;
while (m --) {
int a, b; cin >> a >> b;
d[a] ++, d[b] ++;
p[find(a)] = find(b);
}
if (!isConnected()) cout << "Non-Eulerian";
else if (hasEulerianCircuit()) cout << "Eulerian";
else if (hasEulerianPath()) cout << "Semi-Eulerian";
else cout << "Non-Eulerian";
return 0;
}
|
求欧拉回路
求欧拉回路一般使用Hierholzer算法。
Hierholzer算法的基本流程如下：
- 从任一点开始对图进行dfs遍历
- 遍历过程中经过的边直接删除
- 当一个顶点的出度减为0时， 加入栈中
- dfs结束后， 将栈中元素出栈， 即为一条欧拉回路
伪代码即为：
1
2
3
4
5
6
7
8
| dfs(node u) {
while (!u.edges.empty()) {
node next = u.edges.back();
u.edges.pop_back();
dfs(next);
}
stk.push(u);
}
|
性质一： dfs的起点就是得到的欧拉回路的起点
性质二： 若要求从某起点出发、字典序最小的欧拉回路，
只需要在遍历边时贪心的选择顶点编号最小的边即可，
可以使用排序或优先队列。
例题——重新安排行程
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi]
表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从
JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK
开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且
只能用一次。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reconstruct-itinerary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
Solution 显然这题是有向边求字典序最小的的欧拉回路。
由于顶点是用字符串代表， 所以用哈希表记录每个顶点的出边集。
预先对出边集排序， 在遍历时看最小的出边。
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
| class Solution {
public:
map<string, vector<string>> e;
vector<string> stk;
void dfs(string u) {
while (e[u].size()) {
string ne = e[u].back(); e[u].pop_back();
dfs(ne);
}
stk.push_back(u);
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
for (auto &v : tickets) {
e[v[0]].push_back(v[1]);
}
for (auto &[s, v] : e) {
sort(v.begin(), v.end(), greater<>());
}
dfs("JFK");
reverse(stk.begin(), stk.end());
return stk;
}
};
|