宽度优先搜索(BFS)在无权图中一定能找到最优解,但在有权图中不一定。 这是因为BFS的逐层遍历特性保证了在无权图中找到的路径是最短步数,但无法处理有权图中路径权重的差异。以下是具体分析:
-
无权图中的最优性
BFS通过逐层扩展节点,确保首次访问目标节点时的路径步数最少。例如,在迷宫问题中,BFS总能找到从起点到终点的最短路径(以步数为单位)。 -
有权图的局限性
若图中边有不同权重(如距离、成本),BFS可能错过实际更优的低权重路径。例如,A→B(步数3)和A→C→B(总步数2)中,BFS会优先选择步数更少的后者,但若A→B的权重实际为1,则BFS的结果并非最优。 -
对比其他算法
Dijkstra算法或A*算法通过考虑权重来弥补BFS的不足,适用于有权图的最优路径搜索。
总结:BFS的“最优解”仅限于无权图的最短步数路径,实际应用中需根据问题类型选择算法。