【深度优先搜索】【图论】【推荐】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。

操作二时：如果有重边，经过几次则删除几条。

以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

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。