补图算法中的最短路径

Question

我今天进行了测试（数据结构课程），问题之一是：给定无向，无权图G =（V，E），您需要编写一种算法，该算法对于给定的节点s返回从s到补图中所有节点v'的最短路径。

补图G'=（E'，V'）包含G中任何不共享边的节点之间的边，并且仅包含那些边。

该算法需要在原始图的O（V + E）中运行。

我问了50个不同的学生，甚至没有一个人能正确解决它。

有任何想法吗？非常感谢，巴拉克。

Answer 1

课程人员已发布了该考试的官方答案。

答案是：

“该算法基于经过调整的BFS。对于图中的每个节点，我们将添加2个字段-next和prev。使用这两个字段，我们可以维护两个节点的双链表：L1，L2。算法每次迭代的开始，L1在图中都有所有while节点，而L2为空BFS代码（不进行初始化）为：

在循环的第3-5行，L1包含G中不与u相邻的所有白色节点，换句话说，补数图中与u相邻的所有白色节点。因此，算法的运行时间等于补图上原始BFS的运行时间。时间为O（V + E），因为第4-5行最多执行2E次，而第7-9行最多执行V次（每个节点只能退出L1一次）。”

注意：这是希伯来语翻译的原始解决方案。

希望对您有所帮助，并感谢大家对我的帮助，

巴拉克