Comparisons and explanations · Intermediate

Breadth-first versus depth-first search

Trace queue-based and stack-based graph exploration, separating reachability, shortest edge count, predecessor paths and frontier memory.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Both explore a graph, with different guarantees
  2. Trace four vertices under both rules
  3. BFS guarantees the shortest edge count
  4. Cycle checks need more than one visited flag
  5. Translate width and depth into memory requirements
  6. Ask Logeia about this articleCheck your understanding

Both explore a graph, with different guarantees

Breadth-first search explores near layers first, while depth-first search follows one branch until it must return. With correct vertex and edge management, both can find the region reachable from a source. Their visiting orders and additional guarantees differ. A request to find a path is incomplete until it specifies whether any path suffices or the fewest-edge path is required. Directedness and edge weights matter too. Sharing the word search does not make the procedures interchangeable for every graph problem. State the desired result and the graph model first, then use the ordering property that supports that result rather than treating a familiar traversal as a universal path optimizer.

AspectBFSDFS
Exploration ruleNear layers firstFollow one branch deeply
Frontier mechanismQueueRecursion or explicit stack
Fewest edgesGuaranteed by standard formNot generally guaranteed

Trace four vertices under both rules

Consider edges A→B, A→C and B→D, enumerating B before C. BFS uses a queue and visits A, then B and C, then D. DFS can visit A,B,D before returning to explore C. These orders depend on neighbor enumeration and are not universal alphabetical rules. Record predecessors if a path must be returned. The list of visited vertices is also distinct from a continuous source-to-target path: visiting A,B,C,D does not imply that B→C and C→D exist. This small trace separates frontier discipline, discovery order and path representation. Keeping those outputs separate avoids a common implementation error in which a traversal log is returned as though it were a valid route.

BFS guarantees the shortest edge count

When every edge counts as one step, BFS discovers vertices in layers of distance zero, one, two and so on. The first discovered distance is therefore the shortest edge count. DFS can encounter a target along a long branch before exploring an available shorter route. BFS does not thereby minimize arbitrary total edge weight. If A→D weighs 100 while A→B and B→D each weigh one, fewest edges and smallest weight disagree. Weighted objectives require a suitable method such as Dijkstra or Bellman–Ford under its assumptions. State what the reported distance minimizes. A correct shortest-edge answer can still be the wrong answer to an application asking about travel time or another nonuniform weight.

Cycle checks need more than one visited flag

Discovery tracking prevents repeated work in either traversal. For a directed DFS cycle check, distinguish undiscovered, currently active and finished vertices. An edge back to an active ancestor demonstrates a cycle, while an edge to a finished vertex alone does not. Undirected graphs also require separate handling for the edge back to the parent. The rule that any edge to a visited vertex means a cycle is therefore incorrect. Applications such as topological ordering need further reasoning about finishing order and the DAG assumption. The traversal supplies structure for these algorithms; a single generic visited flag does not automatically establish every property that a more specialized graph analysis requires.

Translate width and depth into memory requirements

With adjacency lists and standard one-time vertex discovery, both traversals run in O(V+E) time and use O(V) auxiliary space including discovery state and predecessors. BFS can retain a wide frontier; DFS can have a deep stack on a long narrow graph. Neither constant-space DFS nor an unconditional rule that BFS always uses more memory is justified. Recursive DFS additionally faces the execution environment’s stack limit. An adjacency matrix changes edge-inspection costs. Compare representation and graph shape along with the required guarantee and path storage. These factors explain the operational difference much better than choosing from one complexity expression while overlooking what is actually retained during exploration.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path