这是面试时问的问题。
面试官要我证明我的解决方案是正确的并且它在 O(|V| + |E|) 中运行
我只是愣住了。
更具体地说，关于为什么这不简单，请考虑以下子问题:
在什么情况下，答案是否定的，我们不能。
首选 BFS 还是 DFS，为什么？
有无向图不是很困难吗？因为我可以来回旅行，所以如果有偶数节点的循环，看来我们真的不能这样做，IMO。
最佳答案
具有此属性的图称为 bipartite graph您可以使用一些不错的算法来测试图是否是二分图。
关于二部图的一个关键定理是，一个图是二部的当且仅当它不包含奇数长度的循环。这个定理真的很有用，因为它意味着如果你最终重新访问了一个你见过的节点，你可以确定它对你是否重要。如果这关闭了一个奇数长度的循环，那么您就知道该图不是二分图并且您已经完成了。否则，如果它关闭了一个偶数长度的循环，您可以忽略它并继续前进。
在此基础上，您可以通过对图进行 DFS 或 BFS 并进行一些小的修改来检查图是否是二分图。首先，跟踪您在搜索中所处的深度。将偶数层的所有节点标记为红色，将奇数层的所有节点标记为黑色。在您进行搜索时，如果您为一个节点分配了一种颜色并注意到它的一个邻居已经被赋予了相同的颜色，那么您就有了一个奇数长度的循环并且您可以报告不存在任何颜色(您明白为什么了吗？ ).如果这种情况永远不会发生，那么您已将每个节点着色为红色或黑色，并且没有两个相邻节点的颜色相同，您就完成了!
由于这会为 BFS 或 DFS 添加恒定数量的每个节点工作量，因此运行时最终与图的大小成线性关系。你可以选择任何你喜欢的搜索算法；选择中的折衷取决于内存使用等其他因素。
就其值(value)而言，二分图是一类非常著名且有用的图，将来可能值得一读。它们有很多很酷的特性和漂亮的应用程序!
关于algorithm - 如何判断无向图是否可以涂成红色或黑色，使得不存在两个连续的红色或黑色，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47141172/