修改 DFS 算法以检查图中的顶点

Question

只需要一个伪代码，不需要整个运行代码。 对 DFS 算法进行所需的修改，以便它可以检查图中的顶点是否可以用 0 和 1 标记，这样具有相同标签的顶点之间没有边。

Answer 1

您要查找的图称为二分图。对 DFS 的修改是这样的（让所有节点的颜色 [节点] 在开始时为 -1）：

• 让颜色[1] = 1。
• 从节点 1 启动 DFS
• 在您的 DFS 中，用与当前节点颜色相反的颜色为当前节点的所有未着色邻居着色。
• 如果存在颜色与当前节点颜色相同的彩色邻居，则无解。