332. 重新安排行程

[dutLyuyu]

332. 重新安排行程

思路

欧拉图

这种「一笔画」问题与欧拉图或者半欧拉图有着紧密的联系，下面给出定义：

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

判别这张图是否是欧拉图或者半欧拉图

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

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

Hierholzer 算法

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

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

当我们顺序地考虑该问题时，我们也许很难解决该问题，因为我们无法判断当前节点的哪一个分支是「死胡同」分支。

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

对于当前节点而言，从它的每一个非「死胡同」分支出发进行深度优先搜索，都将会搜回到当前节点。 而从它的「死胡同」分支出发进行深度优先搜索将不会搜回到当前节点。也就是说当前节点的死胡同分支将会优先于其他非「死胡同」分支入栈。

这样就能保证我们可以「一笔画」地走完所有边，最终的栈中逆序地保存了「一笔画」的结果。我们只要将栈中的内容反转，即可得到答案。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reconstruct-itinerary/solution/zhong-xin-an-pai-xing-cheng-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

按照贪心的方式走，如果走到一个点，发现无法继续走了，并且还有某条边没有走过。则说明之前某一个分岔点上走错了，提前进入了一条无法回头的路。应该先走其它边，最后再走这一条无法回头的路。

把这段已知的无法回头的路去掉，则是一个更小的图。我们假想对这个小的图如何走，起点还是和原来一样，终点必然是刚刚的分岔点（因为分岔点不是终点，其原来的度数原来为偶数，去掉一条边后度数为奇数。）。在这个小的图上得到自然排序最小的答案后，再在最后添加上刚刚去掉的那一段，则是大图上的结果。

这里的逆序添加到结果集确实是最点睛的地方，贪心的情况下可能寻找不了欧拉路径。用Hierholzer 算法分析，入度大于出度的节点必然会第一个添加到结果集，再推广一下来看，也就是Hierholzer 算法第三条加入数组的次序恰好和欧拉回路是倒转的，reverse就行了。

代码

/**
 * @param {string[][]} tickets
 * @return {string[]}
 */



const Node = function(val){
    this.val = val;
    this.next = [];
} 

var findItinerary = function(tickets) {
    const nodeMap = {};
    const result = [];

    const getNodeOrNewOne = (key) => {
        if (!nodeMap[key]) {
            const node = new Node(key);
            nodeMap[key] = node;
        }
        return nodeMap[key];
    }; 


    for(let i = 0; i < tickets.length; i++){
        const relation = tickets[i];
        getNodeOrNewOne(relation[0]);
        getNodeOrNewOne(relation[1]);
        nodeMap[relation[0]].next.push(relation[1]);
        // lexicographical order
        nodeMap[relation[0]].next.sort();
    }

    const loop = (node) => {
        while(node.next.length !== 0) {
            const nextKey = node.next.shift();
            loop(nodeMap[nextKey]);
        }
        result.push(node.val);
    };

    loop(nodeMap['JFK']);
    return result.reverse();
};