算法笔记之欧拉路径——合法重新排列数对
2021-12-13 本文已影响0人
简单一点点
有向图的欧拉路径计算，平时遇到的不多，记录一下。
欧拉图知识
欧拉图就是从任意一个点开始都可以一笔画完整个图，半欧拉图必须从某个点开始才能一笔画完整个图。
性质
对于无向图，欧拉图中所有顶点的度数都是偶数，因为每个点的入度和出度成对出现
对于有向图，欧拉图中所有节点的入度和出度都相等
有向图中存在欧拉通路的两种情况：
- 欧拉通路的起点为入度比出度恰好少 1 的节点，终点为入度恰好比出度多 1 的节点。
- 所有节点的入度和出度都相等（是个环），那么从任意节点开始都存在欧拉通路，也就是欧拉回路。
判别一个图是否为欧拉图
对于无向图， 当且仅当是连通图且没有奇度顶点时，为欧拉图。
对于无向图 ，当且仅当是连通图且图中恰有0个或2个奇度顶点时，为半欧拉图（没有环）。
对于有向图 ，当且仅当所有顶点属于同一个强连通分量且每个顶点的入度和出度相同时，为欧拉图。
对于有向图 ， 当且仅当满足下面条件时，为半欧拉图
- 如果将所有的有向边退化为无向边时，那么所有顶点属于同一个连通分量。
- 最多只有一个顶点的出度与入度差为 1。
- 最多只有一个顶点的入度与出度差为 1。
- 所有其他顶点的入度和出度相同。
Hierholzer 算法
Hierholzer 算法是求解欧拉路径的算法，利用了深度优先搜索和贪心的思想。
Hierholzer 算法流程如下：
- 从起点出发，进行深度优先搜索。
- 每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边（灵魂）。
- 如果当前顶点没有相邻边，则将顶点入栈。
- 栈中的顶点倒序输出，就是从起点出发的欧拉路径。
原理和证明这里就不讲述了。
题目描述
给你一个下标从 0 开始的二维整数数组 pairs ，其中 pairs[i] = [starti, endi] 。如果 pairs 的一个重新排列，满足对每一个下标 i （ 1 <= i < pairs.length ）都有 endi-1 == starti ，那么我们就认为这个重新排列是 pairs 的一个 合法重新排列 。
请你返回 任意一个 pairs 的合法重新排列。
注意：数据保证至少存在一个 pairs 的合法重新排列。
解题思路
欧拉路径的解题有2个地方，一个就是Hierholzer 算法找到路径顺序，前面已经介绍。另一点就是要找到出发点，寻找方法是：
- 如果找到一个点的出度（从该点出发的边的数量）比入度（进入该点的边的数量） 大 1，那么该点毫无疑问是起点；
（如果该点不是起点，那么这个点的边无论如何也遍历不完，因为只有进去一次才能出去一次）;
-如果没找到这样的一个点，那么任何一个点都可以作为起点。（说明是个环路）
Java代码
class Solution {
private List<Integer> path; // 记录路径
private Map<Integer, List<Integer>> map; // 邻接表
public int[][] validArrangement(int[][] pairs) {
map = new HashMap<>();
Map<Integer, Integer> inMap = new HashMap<>(); // 入度
Map<Integer, Integer> outMap = new HashMap<>(); // 出度
for(int[] p : pairs) {
List<Integer> list = map.getOrDefault(p[0], new ArrayList<Integer>());
list.add(p[1]);
map.put(p[0], list);
int a1 = inMap.getOrDefault(p[1], 0);
inMap.put(p[1], a1 + 1);
int a2 = outMap.getOrDefault(p[0], 0);
outMap.put(p[0], a2 + 1);
}
// 找到起始点
int start = pairs[0][0];
for(Map.Entry<Integer, Integer> entry : outMap.entrySet()) {
int a = entry.getValue();
if(!inMap.containsKey(entry.getKey()) || inMap.get(entry.getKey()) < a) {
start = entry.getKey();
break;
}
}
path = new ArrayList<>();
dfs(start);
//注意路径是反的，这里要正过来
Collections.reverse(path);
int[][] r = new int[path.size() - 1][2];
for(int i = 0; i < r.length; i++) {
r[i][0] = path.get(i);
r[i][1] = path.get(i + 1);
}
return r;
}
// 计算欧拉回路
private void dfs(int start) {
if(map.containsKey(start)) {
List<Integer> a = map.get(start);
while(a.size() > 0) {
// 记得删除当前节点
dfs(a.remove(0));
}
}
path.add(start);
}
}
