332. 重新安排行程

通过图论的相关知识可知，题目的要求是通过已知条件建立一个欧拉通路，最常用的算法是Hierholzer算法。

Hierholzer算法

Hierholzer算法给出一种基于dfs寻找欧拉回路的算法

step 1: 选择一个合适的开始node, 对于无向图, 为一个度数为奇数的节点(如果所有点的度数为偶数则随机一点); 对于有向图, 为一个出度比入度多1的节点(如果均相同则为随机一点).
step 2: 从node开始进行深度优先遍历, 对于当前点, 枚举其相邻的顶点, 并删除该边, 递归到相邻顶点(配合代码理解比较直观), 如果与当前顶点相连的所有边都已经被遍历, 将该点加入到队列中, 进行回溯.

void dfs(int node){
    while(g[node].size()){
        int v=*g[node].begin(); // 取出相连边的另一个顶点
        g[node].erase(g[node].begin()); // 先删除边, 再递归
        dfs(v);
    }
    ans.push_back(v); // 顶点加入队列并回溯
}

step 3: 队列中存储着反向欧拉路径/回路.

代码示例

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, multiset<string>> g;
        // build graph
        for(auto &e: tickets) g[e[0]].insert(e[1]);
        vector<string> ans;
        // Hierholzer
        function<void(string)> dfs=[&](string node){
            while(g[node].size()){
                string v=*g[node].begin();
                g[node].erase(g[node].begin());
                dfs(v);
            }
            ans.insert(ans.begin(), node);
        };
        dfs("JFK");
        return ans;
    }
};

作者：minuxAE
链接：https://leetcode.cn/circle/article/Dh85Wa/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。