1.欧拉图
对于一个有向图或无向图G，
如果能够不重复地一次走完所有的边，且起点和终点不需相同，称G含有欧拉路径，G为半欧拉图
如果能够不重复地走完所有的边，且起点和终点相同，即从起点出发不重复地一次走完所有边后再次回到起点，称G含有欧拉回路，G为欧拉图
欧拉图是特殊的半欧拉图
图G是欧拉图的充要条件<——>G有欧拉回路<——>G的每个节点的出入度相同 / G的每个节点的相关边有偶数条
有了上面的条件，不难得到图G是半欧拉图的充要条件：图G是半欧拉图的充要条件<——>G有欧拉路径<——>除起点和终点外，G的每个节点的出入度相同 / 除起点和终点外，G的每个节点的相关边有偶数条
简单来说，欧拉图问题就是常见的图的一笔画问题
当我们遇到一个图结构的问题时，可以看看它是否是一个欧拉图或者半欧拉图。如果是的话，往往可以将问题抽象为求一笔画的路径
2.code model
先看Hierholzer算法
问题简述：现给出一个有向欧拉图。求一个欧拉回路
Hierholzer算法过程：
选择任一顶点为起点。DFS深度优先搜索，访问所有相邻顶点。
将经过的边都"删除"。这里的删除，本质上是指当前的边走过后，不可重复经过。可以通过维护一个set，存储所有已经经过的边，来实现所谓的“删除”效果
如果当前顶点已经没有相邻边，则将顶点【入栈】。
栈中的顶点倒序输出，就是从起点出发的欧拉回路。
求欧拉路径也是同样，只是起点必须是奇数度的顶点，而不能任意顶点，其他不变
伪代码，十分简洁
visited = set()
dfs(node):
for nei in neibors:
# 如果这条边未曾走过
if node-nei not in visited:
# 加入visited集合来模拟删除
visited.add(node-nei)
dfs(nei)
# 遍历完所有邻居后，所有相邻边也被删除，当前顶点已经没有相邻边，【入栈】
stack.push(node)
从代码的结构看，Hierholzer算法就是一个十分标准的【后序遍历DFS】
下面通过图例说明：
image1
这是一个半欧拉图，欧拉路径顺序应该是J-B-J-A
我们从起点J出发，dfs它的所有相邻节点并且把经过的边删除，可能有两种情况
- 从J开始，先访问邻居B，回环边。这时dfs下去会依次删除JB, BJ, JA。这样所有边都删掉了，每个顶点都木有邻居了，根据程序的顺序，A-J-B-J依次入栈
- 从J开始，先访问邻居A，死胡同。这时删除JA，这样顶点A木有邻居了，A入栈；然后从J访问邻居B，dfs下去会依次删除JB, BJ，此时再次来到J，而J没有邻居了，J入栈，然后B入栈，然后J入栈。整体顺序仍然是A-J-B-J
3.对Hierholzer算法的剖析
- 1.【为什么可以递归来实现Hierholzer算法】一个欧拉图，或者一个半欧拉图，假设现在从起点出发来到下一个结点，我们把起点和刚刚经过的边拿掉，剩下的图仍然是一个半欧拉图！。这样，我们可以不断地拿掉一个个起点和走过的边，将图的规模不断地缩小，同时保持了半欧拉图的性质。图的性质未发生改变但问题规模不断缩小，正是递归的思想
- 2.【为什么是后序遍历的DFS】
后序遍历本质上是由欧拉图的特性决定的。以有向半欧拉图为例，除了起点和终点，任何中间节点的出度都等于入度，这意味着从任何一个中间结点出去，都【可以】回到这个结点（除了出入度均为1的情况）。但是，也必然存在这样的情况，从一条出边出去后就再也回不来了，这就是通往终点的必经边，暂且叫死胡同。因此，对于每个结点，存在两种出边：1.若干条回环边 2.一条死胡同。对于当前节点而言，从它的每一个回环边出发进行深度优先搜索，都将会搜回到当前节点。而从它的「死胡同」出发进行深度优先搜索将不会搜回到当前节点。也就是说当前节点的死胡同分支需要最后走——【一言以蔽之，对于每个结点，有环的把所有环走完，最后再走死胡同，这是我理解的Hierholzer算法本质】。问题的关键就在于如何保证那唯一的死胡同最后走，其他的回环边随便走，反正都会回去的。但对不起，作为程序，怎么可能知道哪条是死胡同。那怎么办？那就换个思路，随便选择一条出边走就好了，随便走；但规定，只有当前结点的所有有向邻居结点都被完全出入后，当前结点与所有邻居的边都被删除，此时当前结点作为终点并结算。这样一来，一方面，必然是目标终点首先结算，因为只有它没有有向邻居结点；另一方面，这种后序遍历的操作被视为在不断更新逻辑终点的位置，因为已经结算的部分图的结点不需要再考虑，逻辑终点变成所有有向邻居结点都被结算后的当前结点
我不再正向审视问题，不再正序地必须要求死胡同这条路最后再走；而是反向思考问题，路的顺序已不重要，而只保证逻辑终点最先被结算。这种【后序遍历+栈】的组合拳，用逆向思维保证了正向顺序
4.例题
4.1 leetcode 332. 重新安排行程
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。假定所有机票至少存在一种合理的行程。
示例：
输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
分析：输入list的每一个元素都可以看作一条边，这样题目抽象出来就是一次遍历所有边且不重复，典型的欧拉图问题
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
def dfs(curr: str):
while vec[curr]:
# pop就是删除边了！每走过一条边就删除一条
tmp = heapq.heappop(vec[curr])
dfs(tmp)
# 遍历完所有下一结点后，才将当前结点入栈，保证单度结点最先入栈
stack.append(curr)
vec = collections.defaultdict(list)
# 建立有向图邻接表
for depart, arrive in tickets:
vec[depart].append(arrive)
# 排序
for key in vec:
heapq.heapify(vec[key])
stack = list()
dfs("JFK")
return stack[::-1]
4.2 leetcode 753. 破解保险箱
有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, ..., k-1 中的一个 。
你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。
举个例子，假设密码是 "345"，你可以输入 "012345" 来打开它，只是你输入了 6 个字符.
请返回一个能打开保险箱的最短字符串
示例2:
输入: n = 2, k = 2
输出: "00110"
说明: "01100", "10011", "11001" 也能打开保险箱
分析：
这种单个字符变化的问题，基本上都可以抽象为图问题。但本题的难点在于发现能够抽象为欧拉图问题以及如何抽象成欧拉图。
对于一个n位长度的字符串，我们选择n-1长度的字符串s作为结点，每个结点共有k条出边，每条边分别对应0 - k-1；每个结点共有k条入边，每条边也分别对应0 - k-1。node+出边可以构成s+edge_val的密码，且到达的结点为(s+edge_val)[1:]。例如，n=3, k=2的情况下，结点00和出边1可以构成密码001，而达到结点01.。这样，每个结点都具有k入和k出，明显的欧拉图问题。所求 = 初始结点值+路径序，从任意一个结点开始都可以
欧拉图示例-图片来源于leetcode题解
class Solution(object):
def crackSafe(self, n, k):
walk = set()
ans = []
def dfs(node):
for x in range(k):
end_ele = str(x)
# 结点是node，end_ele表示边，nei表示node的一条出边
nei = node + end_ele
# 如果nei这条边没走过，走它
if nei not in walk:
walk.add(nei)
dfs(nei[1:])
ans.append(end_ele)
dfs("0" * (n-1))
# ans是倒序的，因此"0" * (n-1)加在最后
return "".join(ans) + "0" * (n-1)
网友评论