已知BFS可求无权重无向图最短路径，能否用于无权重有向图？

是的，广度优先搜索（BFS）完全可以用来查找无权重有向图中从源点到目标点的最短路径。

BFS的核心逻辑是按「距离层」遍历节点：从源点出发，先访问所有距离源点1步的节点，再依次访问距离2步、3步的节点……在无权重有向图中，每条边的移动代价都是1，所以当某个节点第一次被访问到时，经过的路径长度必然是最短的——后续任何到达该节点的路径，长度只会更长，不可能更短。

这和无权重无向图的场景本质一致，唯一的区别是有向图的边是单向的：比如节点A到B有边，但B到A不一定存在，遍历的时候只能沿着边的指向去访问相邻节点，但BFS按层扩展的逻辑不受这个限制，只要严格遵循边的方向遍历即可。

举个简单例子：假设有向图的结构是 S → A → T，同时存在另一条路径 S → B → C → T。BFS从S出发，第一层会访问A和B（距离源点1步），第二层会通过A访问到T（距离2步），这时候T的最短路径就确定了，后续通过C到达T的路径长度是3，不会更新最短路径。

需要注意两个前提：

• 必须是无权重图：所有边的权重相同（通常为1），如果有向图存在不同权重的边，BFS就不再适用，此时应该用Dijkstra算法这类适配带权图的方法。
• 处理环的问题：如果有向图存在环，只要环不在源点到目标点的最短路径上，BFS就能正常工作——因为BFS会标记已访问的节点，不会重复遍历环内的节点，避免无限循环。

内容的提问来源于stack exchange，提问作者Divyanshu Dwivedi