创建不包含在 BFS 中的简单路径边

Question

首先...这是问题...

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

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

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

还有其他想法吗？

Answer 1

    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，并且不会将其作为后代添加到生成的广度优先树中。

Answer 2

我不确定你是否只是为了找到一个反例，或者找到一个在任何给定图上运行的算法。找到一个反例并不是很难，比如

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

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

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

Answer 3

这个问题很旧，但我发布了另一个答案，因为它已经被查看了很多次。这是 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。

它之所以有效，是因为 a 和 b 到 x 和 y 的距离相同。如果您先将 x 入队，那么您通过 BFS 的路径将从 x 到 a 和 b。如果你先将 y 入队，那么你通过 BFS 的路径将是从 y 到 a 和 b。在 BFS 中，您不能像解决方案那样混合和匹配。