BFS/DFS中节点加入visited集合的时机：差异与选型咨询

Great question—this is a super common point of confusion when implementing graph traversals, and the timing of marking nodes as visited does have meaningful implications for efficiency and behavior. Let’s break this down clearly:

Two Approaches to Marking Visited Nodes #

First, let’s restate the two methods you described to make sure we’re on the same page:

1. Mark as visited after popping from stack/queue #

• Workflow: Start by adding the initial node to your stack/queue. Then, in each iteration:
  • Pop a node from the stack/queue
  • Mark it as visited
  • Iterate over its neighbors, adding any unmarked nodes to the stack/queue
• Key quirk: A node can be added to the stack/queue multiple times before it’s marked as visited.

2. Mark as visited when adding to stack/queue #

• Workflow: Mark the initial node as visited, then add it to your stack/queue. In each iteration:
  • Pop a node from the stack/queue
  • Iterate over its neighbors, marking any unmarked nodes as visited before adding them to the stack/queue
• Key quirk: A node is only ever added to the stack/queue once.

Core Differences Between the Two Methods #

Let’s dive into the practical differences that matter:

• Duplicate nodes in stack/queue: The first method can lead to the same node being added multiple times. For example, if you have a cycle (like A → B → C → A) or multiple paths to the same node, the unmarked node might be added by multiple neighbors before it’s popped and marked. This means your stack/queue will have redundant entries, which wastes memory and adds unnecessary processing steps (when you pop the duplicate, you’ll just mark it as visited again and skip processing neighbors).
• Efficiency: The second method is almost always more efficient. By marking nodes as visited the moment they’re added, you eliminate duplicate entries entirely. This is especially noticeable in large graphs or graphs with many cycles, where the first method could bloat your stack/queue significantly.
• Correctness: Both methods will correctly traverse all reachable nodes in the graph. Even with duplicates in the first method, once a node is marked as visited after being popped, any subsequent duplicates of that node will be ignored when processed (since you’ll check if it’s visited before handling its neighbors). So you won’t miss any nodes or process them incorrectly—you’ll just do extra work.

Which One Should You Choose? #

In almost all standard graph traversal scenarios (like finding connected components, shortest paths in unweighted graphs with BFS, or general DFS exploration), go with the second method: mark nodes as visited when adding them to the stack/queue. It’s more efficient, cleaner, and avoids the overhead of duplicate nodes.

The only rare cases where you might prefer the first method are niche scenarios where you need to track all possible paths to a node (though even then, there are better ways to handle that than relying on duplicate stack/queue entries) or if you’re working with a specific algorithm that requires delayed marking. But for 99% of everyday BFS/DFS implementations, the second approach is the way to go.

And to confirm your guess: yes, the first method can have issues with cycles in terms of efficiency (duplicate nodes), but it won’t break correctness—you’ll still traverse the graph properly, just with extra work.

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