互补图算法中最短的路径

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一次）。“

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

我希望您发现它有帮助，并感谢大家对我的帮助，

巴拉克。

Answer 2

初始化：-

创建未发现边缘的列表。让我们将其称为undiscovered并使用所有节点对其进行初始化。

然后我们将运行BFS的修改版
1. 创建队列（Q）并向其中添加起始节点

主要算法

未发现时。size（）> 0 &&队列不为空

curr_node = DEQUEUE（队列）

在补图中创建所有边的列表（我们称它为complement_edges）。这可以通过遍历所有undiscovered中的节点并检查它是否已连接到curr_node。
2. 然后循环遍历complement_edges中的每个节点，执行3操作

3. 最佳更新距离

从未发现的节点删除此节点
• ENQUEUE（队列，此节点）

这里有些注意事项，如果初始图稀疏，则undiscovered将很快变空。在实现过程中，使用哈希将边缘存储在图形中，这将使步骤2更快。

这里是示例代码：-

HashSet<Integer> adjList[];           // graph stored as adjancency list

public int[] calc_distance(int start){
        HashSet<Integer> undiscovered = new HashSet<>();
        for(int i=1;i<=N;i++){
            undiscovered.add(i);
        }

        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE/4);


        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        dist[start] = 0;

        while(!q.isEmpty() && undiscovered.size()>0){
            int curr = q.poll();

            LinkedList<Integer> complement_edges = new LinkedList<>();
            for(int child : undiscovered){
                if(!adjList[curr].contains(child)){
                    // curr and child is connected in complement
                    complement_edges.add(child);
                }
            }

            for(int child : complement_edges){
                if(dist[child]>(dist[curr]+1)){
                    dist[child] = dist[curr]+1;
                }
                // remove complement_edges from undiscovered
                undiscovered.remove(child);
                q.add(child);
            }
        }

        return dist;
    }
}