【深度优先搜索】【图论】【推荐】332. 重新安排行程

作者推荐

动态规划的时间复杂度优化

本文涉及知识点

深度优先搜索图论

LeetCode332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

示例 1：
在这里插入图片描述

输入：tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]]
输出：[“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]
示例 2：
在这里插入图片描述

输入：tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]
输出：[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]
解释：另一种有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”] ，但是它字典排序更大更靠后。

提示：
1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi 和 toi 由大写英文字母组成
fromi != toi

基础知识

定义

如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。
如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)。

性质

性质一：一个有向图是欧拉回路 $\iff$ 所有顶点的入度等于出度且该图是连通图。
性质二：一个有向图是欧拉路径 $\iff$ 起点出度等于入度+1，终点入度=出度+1,其它顶点的入度等于出度且该图是连通图。
欧拉路径和回路符合性质比较简单，不证明。下面只证明性质一必定是欧拉回路，性质二是欧拉路径。

证明一

设有向图G符合性质一。
操作一：以任意定点为起点s，选取s的任意临接点n1，删除sn1后，除s外，其它顶点都是出度等于入度，就是进入后，一定会离开。由于顶点的出度和入度是有限的，所以一定会结束，而结束点一定是s（因为只有它入度大于出度）。设删除经过的路径为P1。
最后一次经过s后，可能有些点入度并不为0。
$\rightarrow\begin{cases}**操作二**图G删除P1各边，此时余下的边P2仍然符合性质一。\\ P1经过的各点，一定有点n2出度不为0。否则与连通图矛盾。\\ \end{cases}$
操作二时：如果有重边，经过几次则删除几条。
以n2为起点对P2进行操作一，得到P3，必定以n2开始和结尾。
用P3替换P1的n2节点。如此往复直到所有节点出度入度为0。

证明二

设有向图G符合性质二，s出度=入度+1,e入度=出度+1。一定存在以s为起点,e为终点的路径P1。选取方法类似证明一，多个出边任选一条出边。图G删除P1后，为P2；P2要么为空，要么符合性质二。

深度优先搜索

题目确保某条从JFK为起点的路径是欧拉路径。
如果是欧拉环路：所有点出度等于入度。
如果不是环路：起点出度-1==入度终点入度=出度+1，其它节点入度等于出度。
必须确保起点最后访问终点那一支，其它访问顺序按字典需。

DFS 函数

在这里插入图片描述

主函数

DFS(“JFK”)
颠倒m_vRes的顺序
返回m_vRet。

示例和时序图

在这里插入图片描述

按时间线访问m_vRes的顺序:DAFEACBA。转置（颠倒顺序）后为：ABCAEFAD。

证明：

假定图G的欧拉路径最后一个出度大于1的节点为c，它共有m+1+n条出边，按邻接字典序排序后，第m+1条出边指向终点e。
步骤一：只讨论节点c及之后的路径。设c的临接点按字典序分别为：n[1] …n[m+n+1]。
除DFS(n[1+m] $\rightarrow$ e)可以直接结束，其它节点都必须等所有A的出边都访问结束（包括n[1+m])，所以 n[1+m] $\rightarrow$ e 的逆序最先加到vRet。
c $\rightarrow$ n[n+m+1]是c最后一条出边，故将 n[i+m+1] $\rightarrow$ c 的逆序放到vRet 中。
c $\rightarrow$ n[n+m ]是c最倒数第二条出边，故将 n[i+m] $\rightarrow$ c 的逆序放到vRet 中。
$\cdots$ 将 n[1+m+1] $\rightarrow$ c 的逆序放到vRet 中。
$\vdots$
$\cdots$ 将 n[m] $\rightarrow$ c 的逆序放到vRet 中。
$\cdots$ n[1 ] $\rightarrow$ c 的逆序放到vRet 中。
将c 放到vRet 中。
步骤二：将图G 节点c及之后节点的出边都删除。c变成新的终点。
不断持续步骤一二到所有节点的出度为1。注意：c等于e也符合。

代码

核心代码

class Solution {
public:
	vector<string> findItinerary(vector<vector<string>>& tickets) {
		std::unordered_map<string, multiset<string>> mNeiBo;
		for (const auto& v : tickets)
		{
			mNeiBo[v[0]].emplace(v[1]);
		}
		DFS(mNeiBo, "JFK");
		std::reverse(m_vRet.begin(), m_vRet.end());
		return m_vRet;
	}
	void DFS(std::unordered_map<string, multiset<string>>& mNeiBo,const string& cur)
	{
		while (mNeiBo[cur].size())
		{
			auto next = *mNeiBo[cur].begin();
			mNeiBo[cur].erase(mNeiBo[cur].begin());
			DFS(mNeiBo, next);
		}
		m_vRet.emplace_back(cur);
	}
	vector<string> m_vRet;
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<vector<string>> tickets;
	{
		Solution sln;
		tickets = { {"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"} };
		auto res = sln.findItinerary(tickets);
		Assert({ "JFK","MUC","LHR","SFO","SJC" }, res);
	}
	{
		Solution sln;
		tickets = { {"JFK","SFO"},{"JFK","ATL"},{"SFO","ATL"},{"ATL","JFK"},{"ATL","SFO"} };
		auto res = sln.findItinerary(tickets);
		Assert({ "JFK","ATL","JFK","SFO","ATL","SFO" }, res);
	}
}

2023年4月

class Solution {
public:
	vector<string> findItinerary(vector<vector<string>>& tickets) {		
		for (const auto& v : tickets)
		{
			m_vNeiB[v[0]].emplace(v[1]);
		}
		dfs("JFK");
		std::reverse(m_vRet.begin(), m_vRet.end());
		return m_vRet;
	}
	void dfs(const string& sCur)
	{
		while (m_vNeiB.count(sCur) && m_vNeiB[sCur].size())
		{
			const string sNext = m_vNeiB[sCur].top();
			m_vNeiB[sCur].pop();
			dfs(sNext);
		}
		m_vRet.emplace_back(sCur);
	}
	std::unordered_map < string, std::priority_queue<string, vector<string>, greater<string>>> m_vNeiB;
	vector<string> m_vRet;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛