入度(进入该点的,d-(x))、出度

欧拉通路:遍历所有边

无向图欧拉回路:所有顶点度为偶数
有向图欧拉回路:所有顶点入度等于出度

DFS搜索欧拉回路

可以把两个相交的回路合成更大的回路

写法:删边然后递归,递归以后把边加入路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//递归搜索(深度优先搜索)欧拉回路
void Euler(int u)
{
int v;
for(v = 0; v < n; v++)
{
if(graph[u][v] == 1)
{
graph[u][v] = graph[v][u] = 0;
Euler(v);
path[pc++] = v;
}
}
}
//调用代码
pc = 0;
Euler(s);
path[pc++] = s;
for(i = pc - 1; i >= 0; i--)
printf("%d ", path[i]+1);
DFS 欧拉回路
DFS 欧拉回路