回路问题指的是有向或无向图中的欧拉回路和哈密顿回路问题。

在一个有向或无向图$G$中，所有边都经过一次且仅经过一次的通路称为欧拉通路，若起点与终点相同，则称为欧拉回路。

若一个图有欧拉回路，则称其为欧拉图，否则若其有欧拉通路，称其为半欧拉图。

无向图欧拉通路的判定条件十分简单，只要图没有奇数度的节点或有且仅有两个奇数度的节点且图是连通图。并且显然若有两个奇数度的节点，那么这两个点必定分别是欧拉通路的起终点。

若无向连通图没有奇数度的节点，那么它一定有欧拉回路。注意这是欧拉回路判定的充要条件，因为每个点都可以进出达到平衡。

有向图的欧拉通路判定条件略为复杂，首先它的基图（即去掉方向的无向图）要连通，其次和无向图对应，所有点出入度相等或一个点出度比入度多一另一个点出度比入度少一、其它点出入度相等。起终点判断显然。

与无向图类似，有向图的欧拉回路判定条件为，基图连通且所有点出入度相等。这同样是充要条件。

这些判断方法的定理和推论都来自离散数学，不过多赘述其实是我不会。

方法一：DFS求解

这一方法非常显然，找到一个正确的起点开始DFS，走不通了就回溯，在栈中记录下经过的边的顺序，当走完所有边时结束算法即可。