如何检查一个无向图是否存在奇数长度的环？

Question

我正在尝试寻找一种O（|V| + |E|）时间复杂度的算法，用于检查一个连通无向图是否存在奇数长度的环。我考虑在图上进行广度优先搜索，并尝试为顶点标记黑色和白色，以确保没有两个带有相同颜色标记的顶点是相邻的。

是否有任何已知的更简洁的算法以线性时间解决这个问题？

- user1048858

Answer 1

你的方法是正确的。你无法做得更好。

这种方法之所以有效，是因为在使用BFS时，如果按照它们的深度对顶点进行标记，那么所有的边要么连接相同的标签，要么连接相差一的标签。很明显，如果有连接相同标签的边，则存在奇环。否则，我们可以将所有奇数标签涂成白色，所有偶数标签涂成黑色。

- Petar Ivanov

Answer 2

在初始化中，您还需要将Num[s]设置为0。

- KeithB

Answer 3

也可以使用深度优先搜索（DFS）并对顶点进行编号来完成。

1. Clock=1
2. 从一个顶点's'开始，将其标记为“已访问”并调用Explore(s)

Explore(u)

1. 如果节点u已经被“访问”，那么如果(clock-Num[u])是奇数，则存在奇数环，

   否则将'u'标记为“访问”

2. Num[u]=clock++;

3. 对于所有相邻的节点v

     i) 探索(v)
     ii) clock=Num[u]
   

- Mostafizar