3

首先……问题来了……

举一个有向图 G = (V, E) 的例子，V 中的一个源顶点 s，以及 E 中包含的一组树边 F，使得对于 V 中包含的每个顶点，图中唯一的简单路径 ( V, F) 从 s 到 v 是 G 中的最短路径，但是无论顶点在每个邻接表中如何排序，都不能通过在 G 上运行 BFS 来生成边集 F。

现在......因为这是家庭作业，我不想要一个直截了当的答案，而是更多关于要查看/尝试的想法的想法。但是，这就是我到目前为止所想到的......

我基本上认为我可以创建一个图形，该图形具有到特定顶点的几条最短路径。当然，这些路径之一将在 BFS 中找到。但是，我可以使用替代路线之一来适应 F。但是，让我失望的部分是“无论顶点如何排序”......我不确定如何将其包含在我的过程。我已经尝试过循环，各种不同的方向流，但还没有。

还有其他想法吗？

4

3 回答 3

2 
    3
 s ---- x
 |     /  
1|    / 1
 |   /
 |  /
 y

万一上图不显示

认为

E = { ((s, x) : 3), ((s, y) : 1), ((y, x) : 1) }

其中两个元组是带有权重的有序对。

边集F = { (s, y), (y, x) }包含图的所有顶点。此外，它包含的从 s 到 x 的唯一简单路径是图中从 s 到 x 的最短路径。但是，BFS 永远不会找到 F。

从 s 开始，将发现 x 和 y 并将其标记为灰色。然后，当探索 y 时，它只会找到另一个灰色顶点，即 x，并且不会将其作为后代添加到生成的广度优先树中。

于 2011-05-17T03:28:36.227 回答
1

我不确定您是要找到一个反例，还是要找到在任何给定图上运行的算法。找到一个反例并不是很困难，例如，

  0
 / \
1 2
|\ /|
| x |
|/ \|
3 4

源为 0。边集 F 包含 (0,1) (0,2), (1,3), (2,4)。F 不能由 BFS 生产。

我还没有找到任何图形的通用算法，但也许上面的示例可以提供线索。

于 2011-02-24T08:11:37.147 回答
1

这个问题很老，但我发布了另一个答案，因为它已被多次查看。这是 Cormen/Leiserson/Rivest/Stein 的算法书中的问题 22-2.6，其他人可能会遇到。

上面的回答假设图表是加权的。如果图被视为未加权，BFS 可以在任一响应中生成边集。问题并没有说图是加权的，而在 Cormen 中，它位于关于未加权图的部分中。

这是未加权情况下的解决方案。步骤是：

  1. 取一个从源 s 到 2 个顶点 x 和 y 的图。s 的度数为 2。x 和 y 分别指向 a 和 b，没有其他地方。
  2. BFS 无法访问的树是从 s 到 x，从 x 到 a，然后从 s 到 y，然后从 y 到 b。

It works because a and b have the same distance from x and y. If you enqueue x first, then your path via BFS will be from x to both a and b. If you enqueue y first, then your path via BFS will be from y to both a and b. In BFS you cannot mix and match the way the solution does.

于 2013-04-09T08:12:11.400 回答