修改后的BFS/DFS在友谊网络上的应用

Question

关于图形和友谊网络，我有一个非常有趣的问题。如下：

老师想确保他的学生不要通过确保没有一对彼此认识的人获得相同的作业来作弊。他认为他只能制作两种不同版本的作业来做到这一点。设计算法（伪代码），以测试给定的学生及其连接图是否可能。该算法应基于DFS或BFS。

我使用BFS解决了问题，并通过与已经访问的节点进行比较，

Modified BFS(v)
  
  Mark v as visited
  Enqueue v
  
  While queue is not empty
    Dequeue v
    Assign either homework to v
    
    For all unvisited neighbors a of v
      Give them the opposite homework
      Mark them as visited
      Add them to queue
 
    For all visited neighbors b of v
      Check if their homework is the same as v, terminate if it is
    

该算法似乎适用于小型手工图形，我可以在其中写出每个步骤。它注定要适合所有这些图形吗？如果算法是正确的，那么伪代码也可以接受吗？我对排队/脱水的顺序以及发生的顺序有些不确定，以及我是否可以在没有临时变量的情况下对最后一行进行比较，以跟踪“当前”节点的作业。

我感谢任何帮助/输入，如果您对另一种算法有想法（例如使用DFS），我也很感谢

Answer 1

您犯了一个错误 - 将任何作业分配给V在循环之前进行。

那么，队列中的每个顶点都将已经分配了家庭作业，并且从未选择要分配给邻居的作业。这显然适用于所有连接的图形。这是一个很好的算法。

您还需要处理未连接的图，并在未访问v时，在所有运行bfs（v）的顶点上有一个循环。