首先...这里的问题...创建简单的路径边缘不包含在BFS
给有向图G =（V，E），源点s在V，和一个的一个例子包含在E中的树边F的集合，使得对于包含在V中的每个顶点，从s到v的图（V，F）中的唯一简单路径是G中的最短路径，但是不能生成边集F通过在G上运行BFS，无论每个邻接列表中的顶点是如何排序的。
现在...因为这是作业，我不想要一个直接的答案，但更多的想法的东西来看看/尝试。但是，这是我到目前为止想到的...
我基本上已经认识到，我可以创建一个图形，有几个最短路径到特定的顶点。当然，这些路径之一将在BFS中找到。但是，我可以使用其中一种替代路线来适应F.但是，抛弃我的部分是“无论顶点如何排序”......我不确定如何将它包含到我的处理。我尝试过循环，各种不同的方向流，但还没有。
还有其他想法吗？
我不确定你是否只是找到一个反例，或找到一个运行在任何给定图上的算法。找到一个反例并不很困难，例如，
0
/\
1 2
|\ /|
| x |
|/ \|
3 4
源是0。边集F包含（0,1）（0,2），（1,3），（2， 4）。 F不能由BFS生产。
我还没有找到任何图的通用算法，但也许上面的示例可以提供一个线索。
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的最短路径。但是，F将永远不会被BFS发现。
从s开始，将会发现x和y并标记为灰色。 然后，当探索y时，它只会找到另一个灰色顶点，即x，而不会将其作为后代添加到生成的广度优先树中。
问题是旧的，但我张贴另一个答案，因为它已被多次查看。这是Cormen/Leiserson/Rivest/Stein算法书中的22-2.6问题，很可能会被其他人遇到。
上面的回答假设图是加权的。如果图形被视为未加权，则BFS可以在任一响应中生成边集。问题并不是说图表是加权的，在Cormen中，它是关于未加权图表的一部分。
Here是未加权情况下的解决方案。步骤如下：
它的工作原理是因为a和b距离x和y的距离相同。如果你先排队x，那么通过BFS的路径将从x到a和b。如果你先排队，那么你通过BFS的路径将从y到a和b。在BFS中，您无法混合使用解决方案的方式。
这比比较好的答案，假设图是加权的。 – codeAligned 2017-04-23 22:38:47