欧拉回路（道路）

无向欧拉图：

定义：给定无孤立结点图G，若存在一条路，经过图中海边一次且仅一次，该条路称为欧拉路；若存在一条回路，经过图中海边一次且仅一次，该回路称为欧拉回路。具有欧拉回路的图称作欧拉图。

定理：无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点。欧拉路和欧拉回路的概念，很易推广到有向图中去。

有向欧拉图 ：
定义：给定有向图G，通过图中每边一次且仅一次的一条单向路(回路)，称作单向欧拉路(回路)。
定理：有向图G具有一条单向欧拉回路，当且仅当是连通的，且每个结点入度等于出度。一个有向图G具有单向欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小1。

找欧拉路(或回路)可以用Fleury算法，如下：
(1).找一个出发点P (如果图中有两个奇数度的点话，任取其一，有向图取出度大的那一个)。
(2).找一条与P相连的边，伸展欧拉路(选边的时候应注意，最后再选取断边;断边是：当去掉该边后使得图不连通的边)。
(3).将选出的边所连的另一个点取代P，去掉该边，重复(2)，直至经过所有的边。

Fleury的另一种说法:

（1）任取v0∈V(G)，令P0=v0；

（2）设Pi=v0e1v1e2...eivi已经行遍，按下面方法来从E(G)-{e1,e2,...,ei}中选 取 ei+1：

（a）ei+1与vi想关联； （b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2,...,ei}中的桥.（3）当（2）不能再进行时，算法停止。

可以证明，当算法停止时所得简单回路Pm = v0e1v1e2...emvm（vm=v0）为G中的一条欧拉回路。

打印出欧拉回路

void euler(int cur) {    for (int v=0; v<n; v++)        if (G[u][v] && !vis[u][v]) {            vis[u][v] = vis[v][u] = 1;            euler(v);            printf("%d %d\n", u, v);        }}

尽管上面的代码只适用于无向图，但不难改成有向图：把 vis[u][v] = vis[v][u] = 1 改成 vis[u][v] 即可。

更多：http://www.nocow.cn/index.php/%E6%AC%A7%E6%8B%89%E8%B7%AF