欧拉路

written by oneman233
2019-09-09

首先给出两个定义:

欧拉路径:由i节点到j节点不重复地遍历所有边

欧拉回路:一条起点与终点相同的欧拉路径

无向图中欧拉路径和欧拉回路的存在条件:

欧拉路径:有且仅有两个点度数为奇数(选取两个奇数度数的点作为起点终点即可)

欧拉回路:每个点的度数都为偶数

有向图中欧拉路径和欧拉回路的存在条件:

欧拉路径:最多有一点入度等于出度加一,最多有一点出度等于入度加一,
并且这两点要么同时存在,要么同时不存在(前者作为终点,后者作为起点)

欧拉回路:每个点的入度都等于出度

dfs搜索欧拉路径的模板:

void dfs(int x)
{
	for(int i=1;i<=500;++i)
	{
		if(mp[x][i])
		{
			mp[x][i]--;
			mp[i][x]--;
			dfs(i);
		}
	}
	st.push(x);
}

两条注意:

  1. 不能直接输出x来获得路径,需要处理结束后遍历栈
  2. 这种dfs可以用于有重边的情况,前提是找到正确的起点