重新安排行程

题目链接

题目 给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。

说明:
如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前
所有的机场都用三个大写字母表示(机场代码)。
假定所有机票至少存在一种合理的行程。

示例1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

示例2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

DFS回溯法

本题有几个难点:

  1. 有多重可能,字母序靠前排在前面,如何记录映射关系?
  2. 解空间是一个图而不是树,使用回溯的终止条件是什么?
  3. 回溯过程中,如何遍历一个城市所对应的所有目的地城市?

回溯模板

首先,遇到可以用回溯解决的问题,可以先把框架搭好,再把终止条件,遍历填进去,使得逻辑更加清晰。

def findItinerary(self,tickets):
    path = [] #记录路径
    # res = [] #记录结果
    def backtrack(cur):
        if #终止条件 :
            # res.append(path[:])
            return True

        for 某节点 in 当前节点的所有选择:
            #去掉不合适的选择,剪枝
            path.append(某节点) #选择
            if backtracking(某节点) #进入下一层
                return True
            path.pop() #取消选择
        return False
    backtrack(cur) #从头节点开始
    return path

问题1:有多重可能,字母序靠前排在前面,如何记录映射关系?

  • 以{key:list}的形式记录起飞点到目的地的映射,并对list进行排序
import collections
import heapq
ticket_dict = collections.defaultdict(list)
tickets=[["JFK","NRT"],["JFK","KUL"],["NRT","JFK"]]
for depart,arrive in tickets:
    ticket_dict[depart].append(arrive)
print(ticket_dict)

for key in ticket_dict:
    ticket_dict[key].sort()
print(ticket_dict)

输出:
defaultdict(<class 'list'>, {'JFK': ['NRT', 'KUL'], 'NRT': ['JFK']})
defaultdict(<class 'list'>, {'JFK': ['KUL', 'NRT'], 'NRT': ['JFK']})

这样就可以直接遍历的结果就是最优解,而不需要考虑多个解并判断字母序。

问题2:终止条件是什么?

以本体为例,可以想象,按照一条可行的路径飞行,到最后一个目的地时,我们手中的机票也正好用完,经过的城市数应该是路径数+1(机票数+1),因此我们的终止条件也显而易见了,当path的长度为机票数+1时终止。

问题3:如何遍历一个城市对应的所有目的地城市?

如果我们正常遍历,势必会出现这种情况,遍历城市A的下一个城市B,但是,B的下一个城市也可以是A,这样就出现了死锁,这在回溯问题中十分常见,因此我们或记录当前走过的城市,或将走过的节点进行删除,防止出现循环路径。

解题代码

import collections
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        path=[] #记录路径
        #记录映射
        ticket_dict=collections.defaultdict(list)
        for depart,arrive in tickets:
            ticket_dict[depart].append(arrive)            
        path=['JFK']
        def backtrack(cur_from):
            #终止条件
            if len(path) == len(tickets) + 1:
                return True
            #遍历下一层
            ticket_dict[cur_from].sort()
            for _ in ticket_dict[cur_from]:
                #删除当前节点,因为排序过了,只用pop第一个就可以
                cur_to=ticket_dict[cur_from].pop(0)
                #做选择
                path.append(cur_to)
                if backtrack(cur_to):
                    return True
                path.pop() #删除选择
                ticket_dict[cur_from].append(cur_to) #恢复当前节点
            return False
        
        backtrack('JFK')
        return path

欧拉回路/欧拉通路

对本题进行化简:给定n各点和m条边的图,要求从指定节点出发,经过所有边恰好一次,也可以理解为给定起点的一笔画问题,且路径的字典序最小。

「一笔画」问题解析

相关定义:

  • 通过图中所有边恰好一次,且行遍所有顶点的通路为欧拉通路。
  • 通过图中所有边恰好一次,且行遍所有顶点的回路为欧拉回路。
  • 具有欧拉回路的无向图成为欧拉图
  • 具有欧拉通路但不具有欧拉回路的无向图为半欧拉图

如果没有保证至少存在一种合理的路径,我们需要判别这张图是否是欧拉图或者半欧拉图,具体地:

  • 对于无向图G,G是欧拉图当且仅当G是连通的且没有奇度顶点。
  • 对于无向图G,G是半欧拉图当且仅当G是连通的且G中恰有2个奇度顶点。
  • 对于有向图G,G是欧拉图当且仅当G的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。
  • 对于有向图G,G是半欧拉图当且仅当G的所有顶点属于同一个强连通分量且
    • 恰有一个顶点的出度与入度差为1;
    • 恰有一个顶点的入度与出度差为1;
    • 所有其他顶点的入度和出度相同。

引用力扣的图引用力扣的图

这种情况下使用贪心算法时,会出现死胡同,从JFK出发,访问AAA时,无法继续访问,但此图满足半欧拉图的条件,存在欧拉通路。

Hierholzer算法

算法思路
Hierholzer算法用于在连通图中寻找欧拉路径,其流程如下:

  1. 从起点出发,进行深度优先搜索。
  2. 每次沿着某条边从某个顶点移动到另外一个顶点的时候,都要删除这条边。
  3. 如果,没有可移动的路径,则将所在节点加入到栈中,并返回。

我们注意到只有那个入度与出度差为1的节点会导致死胡同。而该节点必然是最后一个遍历到的节点。我们可以改变入栈的规则,当我们遍历完一个节点所连的所有节点后,我们才将该节点入栈(即逆序入栈)

对于当前节点而言,对它的非「死胡同」的遍历并将回到当前节点,而从「死胡同」分支出发进行dfs将不会回到当前节点,也就是当前节点的「死胡同」分支将会优先于其非「死胡同」分支入栈。

import collections
import heapq
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        path=[] #记录路径
        #记录映射
        ticket_dict=collections.defaultdict(list)
        for depart,arrive in tickets:
            ticket_dict[depart].append(arrive)
        for key in ticket_dict:
            heapq.heapify(ticket_dict[key])         
        path=[]
        def dfs(cur_from):
            while ticket_dict[cur_from]:
                cur_to=heapq.heappop(ticket_dict[cur_from])
                dfs(cur_to)
            path.append(cur_from)
        dfs('JFK')
        return path[::-1]