小编hex*_*nal的帖子

我之前参加了考试,有一个问题困扰着我和我交谈的其他人.它问了以下问题:

给出一个未加权的图G和两个顶点s和f的例子,这样s和f之间有一条最短路径,即广度优先搜索(从s开始)将永远不会找到,无论它访问邻近的顶点的顺序如何特别的优势.

对我们来说,这似乎不可能.我的第一个想法是,如果最短路径包含一个顶点作为其第n个步骤,可以从s以m步长到达,其中m < n,那么BFS将永远不会找到该路径,因为顶点已经被标记为参观.但如果是这种情况,所述路径根本不是最短路径,因为通过以m步进入顶点然后继续正常而获得的路径更短.

我们的教授提出了一个不可能的问题(可能是一个错字),还是我错过了什么？

编辑:为了消除任何可能的歧义,问题并没有要求举例说明BFS无法找到从s到f的最短路径.相反,它要求给出一个例子,其中存在从S到f的一些最短路径,BFS将永远找不到.因此,BFS完整且最优的事实并不排除这种可能性,除非我误解了这些术语的含义.

编辑2:也可以假设我们正在使用的BFS算法不会两次处理同一节点.例如,请参阅BFS Wiki上的算法大纲.