友情网修改BFS/DFS的应用
Application of modified BFS/DFS on a friendship network
关于图表和友谊网络，我有一个非常有趣的问题。如下：
一位老师想通过确保没有一对相互认识的人得到相同的家庭作业来确保他的学生没有作弊。他相信他可以通过只做两个不同版本的作业来做到这一点。设计一个算法（伪代码）来测试给定的学生图及其连接是否可行。算法应该是基于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
这个算法似乎适用于手工制作的小型图表，我可以在其中写出每一步。它一定适用于所有此类图表吗？如果算法正确，伪代码是否也可以接受？我有点不确定 queueing/dequeuing 的顺序以及它何时发生以及我是否可以在最后一行进行比较而没有临时变量来跟踪“当前”节点的作业.
我将不胜感激 help/input 如果您对其他算法有想法（例如使用 DFS），我也将不胜感激
你犯了一个错误 -- assign either homework to v 在循环之前。
然后队列中的每个顶点都已经分配了作业，并且永远不会选择将哪些作业分配给邻居。这显然适用于所有连接的图形。算法不错
您还需要处理未连接的图，在未访问 v 时对运行 BFS(v) 的所有顶点进行循环。
关于图表和友谊网络，我有一个非常有趣的问题。如下：
一位老师想通过确保没有一对相互认识的人得到相同的家庭作业来确保他的学生没有作弊。他相信他可以通过只做两个不同版本的作业来做到这一点。设计一个算法（伪代码）来测试给定的学生图及其连接是否可行。算法应该是基于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
这个算法似乎适用于手工制作的小型图表，我可以在其中写出每一步。它一定适用于所有此类图表吗？如果算法正确，伪代码是否也可以接受？我有点不确定 queueing/dequeuing 的顺序以及它何时发生以及我是否可以在最后一行进行比较而没有临时变量来跟踪“当前”节点的作业.
我将不胜感激 help/input 如果您对其他算法有想法（例如使用 DFS），我也将不胜感激
你犯了一个错误 -- assign either homework to v 在循环之前。
然后队列中的每个顶点都已经分配了作业，并且永远不会选择将哪些作业分配给邻居。这显然适用于所有连接的图形。算法不错
您还需要处理未连接的图，在未访问 v 时对运行 BFS(v) 的所有顶点进行循环。