1. 关键：directed graph & visit each path exactly once
2. 涉及的图论知识：Eulerian path
2.1 什么graph才有Eulerian Path？
- 在无向图中，所有顶点的度数均为偶，则存在 Eularian cycle；若有且仅有两个顶点的度数为奇，其余的都为偶，则存在 Eularian path；
- 在有向图中，所有顶点的入度数等于出度数，则存在 Eularian cycle；若有且仅有两个顶点：其中2一个入度数比出度数大 1，另一个入度数比出度数小 1，其余的顶点入度数等于出度数，则存在 Eularian path.
3. 算法：Hierholzer's algorithm
3.1 思想
参考1：欧拉回路
Hierholzer's algorithm
参考2: leetcode dis
Hierholzer's algorithm
首先从起点JFK出发，dfs找到一个sub-path: JFK->A->C->D->A，在A处出现dead end(不再有可以走的边)，此时将A加到解当中，dfs返回。对于返回到的节点D，还有可以继续走的subpath，dfs继续找，得：D->B->C->JFK->D。此时的D为dead end，说明可以将D加到解当中，而且处于已经加过的点之前。以此类推，每次都加dead end的节点。直到所有点都是dead end！
网友评论