技术问询：无权重有向图中DFS能否生成最小生成树及最短路径？

First, let's clear up a small terminology mix-up to make sure we're on the same page:

BFS in an unweighted directed graph is used to find single-source shortest paths and generates a shortest path tree—not a minimum spanning tree (MST). MSTs are primarily a concept for undirected connected graphs (think Prim's or Kruskal's algorithms), so let's focus on shortest paths and path trees here.

Now, to your core question: No, standard DFS can't reliably replicate BFS's ability to find shortest paths or generate a shortest path tree in an unweighted directed graph. Here's why:

• BFS is purpose-built for shortest paths: BFS explores nodes level by level. Starting from your source node, it first visits all nodes 1 step away, then all nodes 2 steps away, and so on. When a node is first discovered, the path taken to reach it is guaranteed to be the shortest possible—any shorter path would have been found in an earlier traversal level, no exceptions.
• DFS prioritizes depth over brevity: DFS follows a single path as far as it can go before backtracking. That means it might stumble onto a node via a long, winding path first, and once that node is marked as visited, standard DFS won't circle back to check for a shorter, more direct route.

Let's use a super simple example to drive this home:
Say we have a directed graph with edges: s → a, s → b, a → b

• BFS will visit s, then immediately hit a and b (both 1 step from s). The shortest path to b is straight from s—no detour needed.
• If DFS picks a first, it'll go s → a → b. The path it records for b is 2 steps long, even though the direct s → b edge exists. Once b is marked as visited, DFS won't go back to check that shorter path.

That said, DFS does generate a depth-first search tree during traversal, but this tree's paths reflect the order of deep exploration, not the shortest possible routes between nodes and the source.

If your goal is shortest paths in an unweighted graph, BFS is your go-to. DFS shines for other tasks: detecting cycles, topological sorting, exploring every possible path (not just the shortest), or checking connectivity in a different way.

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