「一笔画」问题与欧拉图或者半欧拉图有着紧密的联系,下面给出定义:
通过图中所有边恰好一次且行遍所有顶点的通路称为 欧拉通路;
通过图中所有边恰好一次且行遍所有顶点的回路称为 欧拉回路;
具有欧拉回路的无向图称为 欧拉图;
具有欧拉通路但不具有欧拉回路的无向图称为 半欧拉图。
对于无向图 G,G 是欧拉图当且仅当 G 是连通的且没有奇度顶点。
对于无向图 G,G 是半欧拉图当且仅当 G 是连通的且 G 中恰有 0 个或 2 个奇度顶点。
对于有向图 G,G 是欧拉图当且仅当 G 的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。
对于有向图 G,G 是半欧拉图当且仅当 如果将 G 中的所有有向边退化为无向边时,那么 G 的所有顶点属于同一个强连通分量;最多只有一个顶点的出度与入度差为 1;最多只有一个顶点的入度与出度差为 1;所有其他顶点的入度和出度相同。
Hierholzer 算法 的精髓是当每次访问一条边的时候,删除这条边,当遍历完一个节点所连的所有节点后,才将该节点入栈,最后将栈中的节点反转,即可得到欧拉路径。
把数组 pairs 中出现的每个 数 看成一个节点