首先……问题来了……
举一个有向图 G = (V, E) 的例子,V 中的一个源顶点 s,以及 E 中包含的一组树边 F,使得对于 V 中包含的每个顶点,图中唯一的简单路径 ( V, F) 从 s 到 v 是 G 中的最短路径,但是无论顶点在每个邻接表中如何排序,都不能通过在 G 上运行 BFS 来生成边集 F。
现在......因为这是家庭作业,我不想要一个直截了当的答案,而是更多关于要查看/尝试的想法的想法。但是,这就是我到目前为止所想到的......
我基本上认为我可以创建一个图形,该图形具有到特定顶点的几条最短路径。当然,这些路径之一将在 BFS 中找到。但是,我可以使用替代路线之一来适应 F。但是,让我失望的部分是“无论顶点如何排序”......我不确定如何将其包含在我的过程。我已经尝试过循环,各种不同的方向流,但还没有。
还有其他想法吗?