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