欧拉回路&欧拉通路判断

时间:2021-04-30 16:03:22

欧拉回路:图G,若存在一条路,经过G中每条边有且仅有一次,称这条路为欧拉路,如果存在一条回路经过G每条边有且仅有一次,

称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。

判断欧拉通路是否存在的方法

有向图:图连通,有一个顶点出度大入度1,有一个顶点入度大出度1,其余都是出度=入度。

无向图:图连通,只有两个顶点是奇数度,其余都是偶数度的。

判断欧拉回路是否存在的方法

有向图:图连通,所有的顶点出度=入度。

无向图:图连通,所有顶点都是偶数度。

程序实现一般是如下过程:

1.利用并查集判断图是否连通,即判断p[i] < 0的个数,如果大于1,说明不连通。

2.根据出度入度个数,判断是否满足要求。

3.利用dfs输出路径(套圈法)。