首先...這裏的問題...創建簡單的路徑邊緣不包含在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