332. Reconstruct Itinerary

key tips

属于欧拉路径问题

欧拉路径问题

• 欧拉回路：
  遍历图中所有的边，每条边只遍一次，并且回到开始节点
• 欧拉路径
  遍历图中所有的边，每条边只遍历一次

存在性充要条件

• 无向图：
  欧拉路径：所有节点度数为偶数，有0/2个节点度数为奇数
  欧拉回路：所有节点度数为偶数

• 有向图
  欧拉路径：所有节点出度等于入度，有一个节点入度比出度大1，有一个节点入度比出度小1
  欧拉回路：所有节点出度等于入度

算法

算法1 Fleury's algorithm

算法2 Hierholzer's algorithm

算法步骤：
从节点u开始，当u的邻接节点不为空时，选取邻接节点其中一个节点v，将v从u的邻接节点中删除，以v为根结点进行dfs遍历。当u的邻接节点均遍历完成后，将u加入到最终的路径中。

NOTE：似乎只能应用于存在欧拉回路的图中