BFS 不可能找到的最短路径？
Shortest paths that are impossible for BFS to find?
我早些时候参加了一次考试，有一个问题让我和所有与我交谈过的人都感到困惑。它询问了以下内容：
Give an example of an unweighted graph G and two vertices s and f such that there is a shortest path between s and f that breadth-first search (beginning at s) will never find, regardless of the order it visits the vertices adjacent to a particular edge.
对我们来说，这似乎是不可能的。我的第一个想法是，如果最短路径包含一个顶点作为其第 n 步，则可以从 m 步到达s，其中 m<n，那么 BFS 将永远找不到该路径，因为顶点已经被标记为访问过。但如果是这样的话，所述路径根本就不是最短路径，因为通过以 m 步到达顶点然后继续正常进行会获得更短的路径.
我们的教授是不是提出了一个不可能的问题（可能是打字错误），还是我遗漏了什么？
编辑：为了消除任何可能的歧义，问题不要求给出 BFS 无法从 s[= 找到最短路径的示例35=] 到 f。相反，它要求给出一个例子，其中存在 some 从 s 到 f BFS 的最短路径永远找不到。因此，BFS 是完备且单独最优的事实并不排除这种可能性，除非我误解了这些术语的含义。
编辑 2: 也可以假设我们正在使用的 BFS 算法不会处理同一个节点两次。例如，参见 BFS Wiki.
上的算法大纲
例子
设G = (V,E)一个图表
V = ℕ ∪ {-1, 0} 和 E = { {-1,t}, {t,0} | t ∈ ℕ }
让 s = -1 和 f = 0。从s到f存在无限多条长度为2的路径，但由于s有无限多的邻居，BFS永远不会到达f。
不可能有有限的例子
不存在有限图，因此BFS找不到从s到f的最短路径。假设 G 是一个有限图并且 s = a₀ → a₁ → ... → a<sub>n</sub> → a<sub>n+1</sub> = f是从s到f的最短路径。然后存在一个 BFS 的执行顺序，如下所示：
For all i from 0 to n visit a<sub>i+1</sub> first and then all other direct neighbors of a<sub>i</sub>.
由于G是一个有限图，因此每个节点a<sub>i</sub>也只存在有限多个直接邻居。因此它将完成列表并到达路径上的下一个节点。由于该路径是最短路径，因此它是第一个被发现连接 s 和 f 的路径。所以不存在有限图使得 BFS 找不到从 s 到 f.
的最短路径
路径不能短于两条边
也不能有从s到f的路径小于2的例子。
如果认为 s 和 f 不是同一节点，那么可以想到的最短路径的长度为 1。但这意味着 f 是 s 的直接邻居，因此存在一个 BFS 首先访问 f，然后继续访问无限数量的其他邻居。
我认为@hexaflexagonal 可能说错了问题。
应该是CLRS的问题：
问题及解决方案：
由于BFS的性质，有些E_{\pi}的集合不会被BFS生成。具有多个最短路径解的循环图就是这种情况。
我早些时候参加了一次考试，有一个问题让我和所有与我交谈过的人都感到困惑。它询问了以下内容：
Give an example of an unweighted graph G and two vertices s and f such that there is a shortest path between s and f that breadth-first search (beginning at s) will never find, regardless of the order it visits the vertices adjacent to a particular edge.
对我们来说，这似乎是不可能的。我的第一个想法是，如果最短路径包含一个顶点作为其第 n 步，则可以从 m 步到达s，其中 m<n，那么 BFS 将永远找不到该路径，因为顶点已经被标记为访问过。但如果是这样的话，所述路径根本就不是最短路径，因为通过以 m 步到达顶点然后继续正常进行会获得更短的路径.
我们的教授是不是提出了一个不可能的问题（可能是打字错误），还是我遗漏了什么？
编辑：为了消除任何可能的歧义，问题不要求给出 BFS 无法从 s[= 找到最短路径的示例35=] 到 f。相反，它要求给出一个例子，其中存在 some 从 s 到 f BFS 的最短路径永远找不到。因此，BFS 是完备且单独最优的事实并不排除这种可能性，除非我误解了这些术语的含义。
编辑 2: 也可以假设我们正在使用的 BFS 算法不会处理同一个节点两次。例如，参见 BFS Wiki.
上的算法大纲例子
设G = (V,E)一个图表
V = ℕ ∪ {-1, 0} 和 E = { {-1,t}, {t,0} | t ∈ ℕ }
让 s = -1 和 f = 0。从s到f存在无限多条长度为2的路径，但由于s有无限多的邻居，BFS永远不会到达f。
不可能有有限的例子
不存在有限图，因此BFS找不到从s到f的最短路径。假设 G 是一个有限图并且 s = a₀ → a₁ → ... → a<sub>n</sub> → a<sub>n+1</sub> = f是从s到f的最短路径。然后存在一个 BFS 的执行顺序，如下所示：
For all
ifrom0tonvisita<sub>i+1</sub>first and then all other direct neighbors ofa<sub>i</sub>.
由于G是一个有限图，因此每个节点a<sub>i</sub>也只存在有限多个直接邻居。因此它将完成列表并到达路径上的下一个节点。由于该路径是最短路径，因此它是第一个被发现连接 s 和 f 的路径。所以不存在有限图使得 BFS 找不到从 s 到 f.
路径不能短于两条边
也不能有从s到f的路径小于2的例子。
如果认为 s 和 f 不是同一节点，那么可以想到的最短路径的长度为 1。但这意味着 f 是 s 的直接邻居，因此存在一个 BFS 首先访问 f，然后继续访问无限数量的其他邻居。
我认为@hexaflexagonal 可能说错了问题。
应该是CLRS的问题：
问题及解决方案：
由于BFS的性质，有些E_{\pi}的集合不会被BFS生成。具有多个最短路径解的循环图就是这种情况。