一笔画问题

有向图中欧拉路径的判定

在一个有向图中存在欧拉路径要满足以下两个条件：

  1. 图是连通的
  2. 所有定点的入度等于出度（此时存在欧拉回路，以任意顶点出发都可以找到一条欧拉路经回到其本身），或者有且仅有一个点的入度比出度少1（作为欧拉路径的起点），同时有且仅有一个点的入度比出度多1（作为欧拉回路的终点），其余点的入度等于出度。

Hierholzer算法求解欧拉路径

Hierholzer算法用于在连通图寻找欧拉路径，其流程非常简单。

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

1
2
3
4
5
6
7
8
void dfs(Node node, Deque trace){
	while(!node.edges.isEmpty())
	{
		Node next = node.edges.removeLast();
		dfs(next, trace);
	}
	trace.addLast(node);
}

最后从栈顶到栈低依次就是这个图的从起点到终点的欧拉路径。