7

如果您有一个简单的无向图G(V,E)，并且F它是V. 你怎么能找到某个节点v，使得每个节点F到v的距离相同并且距离最小？None如果没有就返回v。有人告诉我，这可以O(|V|+|E|)复杂地完成。

假设所有边的距离为 1。

谁能解释如何做到这一点？伪代码也会有所帮助。

4

2 回答 2

3

这是一种算法，采用伪代码，试图添加注释来解释它是如何工作的。

declare explored // a table of all the vertices that can keep track of one number (distance, initialized to -1) and a list of vertex references (origins, initialized to null)
to_explore = S  // fifo queue of vertices to explore

while (to_explore not empty) {
    pop vertex v from to_explore
    current_distance = explored[v].distance
    current_origins = explored[v].origins
    for (vertex n, neighbor of v) {
        if (explored[n].origins contains v)
            continue // we just hit a loop and we're only interested in shortest distances
        if (explored[n].distance == -1) { // first time we come here
            explored[n].distance = current_distance+1
            explored[n].origins = current_origins
            push n to to_explore
            continue
        }
        if (explored[n].distance != current_distance+1) {
            continue // we are merging path from another node of S but different distance, cannot lead to any solution
        }
        // only case left is explored[n].distance == current_distance+1
        // so we've already come here from other place(s) in S with the same distance
        add / merge (without duplicates) origins to explored[n].origins
        if (explored[n].origins = S) // maybe compare the size is enough?
            return n // we found a solution
        // if not , we just continue our exploration, no need to add to the queue since we've already been through here before
    }
}

这个想法是，使用 FIFO 队列，我们​​将探索距离集合 S 距离为 1 的所有内容，如果我们无法在那里找到任何解决方案，那么我们将首先找到最短距离。

我不完全确定复杂性，但我相信在最坏的情况下，我们只探索每个顶点和每条边一次，这样就可以得到O(|E| + |V|). 但在某些情况下，我们会多次访问同一个顶点。虽然这并没有增加太多探索的路径，但我不确定是否应该有一个因素 |S| 某处（但如果这只是被认为是一个常数，那么没关系......）

希望我没有错过任何东西。显然我没有测试任何这些...... :)

编辑（回复评论）

您的代码是否适用于这样的图表？E = (a, b), (a, c), (a,d) , (b,e), (c,e), (d, e) 和我的 F = { b, c, d}。比如说，你以 a 开始你的 bfs。我怀疑，最后 origins 数组将只有 {a}，因此代码将返回 None。– 大师德瓦拉

在这种情况下，会发生以下情况：

to_explore is initialized to {b,c,d}
//while (to_explore not empty)
pop one from to_explore (b). to_explore becomes {c,d}
current_distance=0
current_origins={b}
//for (neighbors of b) {
handling 'a' as neighbor of b first
explored[a].distance=1
explored[a].origins={b}
to_explore becomes {c,d,a}
//for (neighbors of b)
handling 'e' as next neighbor of b
explored[e].distance=1
explored[e].origins={b}
to_explore becomes {c,d,a,e}
//while (to_explore not empty)
pop one from to_explore (c). to_explore becomes {d,a,e}
current_distance=0
current_origins={c}
//for (neighbors of c)
handling 'a' as neighbor of c first
explored[a].distance is already 1
explored[a].origins={b,c}
to_explore already contains a
//for (neighbors of c) {
handling 'e' as next neighbor of b
explored[e].distance is already 1
explored[e].origins={b,}
to_explore already contains e
//while (to_explore not empty)
pop one from to_explore (d)
current_distance=0
current_origins={d}
//for (neighbors of d)
handling 'a' as neighbor of d first
explored[a].distance is already 1
explored[a].origins={b,c,d}
that matches F, found a as a solution.
于 2013-03-29T04:41:20.860 回答
3

解决方案与 BFS 类似，但略有不同：

  1. 从 S = F 开始，标记 F 个节点。

  2. 查找 |S| 与 S 中每个元素的距离为 1 的集合（所有这些集合都应包含未标记的节点）。如果这些集合的交集不为空，则找到候选。

  3. 取 |S| 的并集 在上面的 S' 中设置并标记这些节点。如果 S' 为空，则返回 'None'。

  4. 返回步骤 2。

假设所有的集合操作都花费恒定的时间，那么算法的复杂度与 BFS 相同，即 O(|V| + |E|)。

现在来推理集合操作的复杂性。我的理由是集合操作不会增加复杂性，因为步骤 2 和 3 中的并集和交集操作可以组合起来花费时间 O(|S|)，并且因为在每个步骤中，S 都不同于先前迭代中的 S ，集合操作的整体复杂度为 O(|V|)。

于 2013-03-26T23:22:49.833 回答