use*_*858 8 algorithm graph
我试图找到一个O(| V | + | E |)时间算法来检查连接的无向图是否具有奇数长度的循环.
我正在考虑在图形上进行宽度优先搜索并尝试将顶点标记为黑色和白色,这样就不会有两个标有相同颜色的顶点相邻.
是否有任何已知的neater算法在线性时间内解决这个问题？
Pet*_*nov 9
你的方法是正确的.你不能做得更好.
有效的原因是,如果在执行BFS时按顶点标注顶点,则所有边连接相同的标签或不同的标签.很明显,如果边缘连接相同的标签,则存在奇数周期.如果没有,那么我们可以将所有奇数标签着色为白色,所有均匀标签为黑
归档时间：
14 年，10 月 前
查看次数：
5227 次
最近记录：
9 年，6 月 前