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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

原文链接: https://www.cnblogs.com/LYX-Blogs/p/17041281.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

    332. 重新安排行程

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/311023

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月16日 上午11:49
下一篇 2023年2月16日 上午11:50

相关推荐