I have a very intresting problem regarding graphs and friendship networks. It is as follows:

A teacher wants to make sure that his students aren't cheating by making sure no pair of people who know each other get the same homework. He believes he can do this by making only two different versions of the homework. Design an algorithm (pseudo code) to test whether this is possible or not for a given graph of students and their connections. The algorithm should be based on DFS or BFS.

I approached the problem using BFS and modifying it by comparing to already visited nodes

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
    

This algorith seems to work for small handmade graphs where i can write out every step. Is it bound to work for all such graphs? If the algorithm is correct, is the pseudo code also acceptable? I am a little uncertain regarding the order of queueing/dequeuing and when it happens as well as whether or not i can make the comparison on the last row without maybe a temporary variable to keep track of the homework for the "current" node.

I wold appreciate any help/input and if you have ideas for another algorithm (for example using DFS), i would appreciate that as well

CodePudding user response：

You made a mistake -- the assign either homework to v goes before the loop.

Then every vertex in the queue will already have homework assigned, and there is never any choice as to which homework to assign to neighbors. This obviously works for all connected graphs. It's a good algorithm.

You need to handle unconnected graphs as well, with a loop over all vertices that runs BFS(v) when v is unvisited.