Exploring Trees and Graphs

Depth-First Search

Depth-first search commits fully to one direction before exploring any other. Starting from a node, it follows one outgoing edge to a neighbor, then one from that neighbor, continuing in this way until it reaches a node with no unvisited neighbors. Only then does it backtrack and try a different direction.

Because of this commitment, DFS reaches distant nodes quickly but makes no guarantee about the distance at which it finds them. A DFS from node A may reach node Z before it has visited all of A’s immediate neighbors. If the goal is to find any path to Z, DFS will find one efficiently. If the goal is to find the shortest path to Z, DFS provides no such guarantee — it will find a path, but not necessarily the shortest one.

DFS is naturally expressed as a recursive algorithm. The recursive structure mirrors the traversal structure: visiting a node means visiting the node itself and then recursively visiting each of its unvisited neighbors. This correspondence between the algorithm’s structure and the data’s structure is why DFS is the natural choice for operations over trees and hierarchies — structures that are themselves recursively defined. Computing the depth of a tree or evaluating an expression tree is a DFS computation, and it reads clearly as recursive code.

DFS is also the natural choice for exhaustive exploration — when the goal is to visit every reachable node, not to find a specific one quickly. Cycle detection and topological sorting of a directed acyclic graph are both DFS computations. They require visiting all reachable nodes, and DFS’s commitment to depth makes it efficient for this class of problem.

Breadth-First Search

Breadth-first search visits nodes in order of their distance from the starting node, measured in the number of edges traversed. It visits all of the start node’s neighbors before visiting any of their neighbors, and all of those before visiting any of their neighbors’ neighbors. It expands outward in concentric layers, one hop at a time.

As a result, BFS finds the nearest node matching any criterion before it finds more distant ones. If the goal is to find the shortest path — in terms of hops — from A to any node satisfying a condition, BFS is guaranteed to find the shortest such path. DFS makes no such guarantee.

BFS is naturally implemented iteratively, using a queue. The queue holds the frontier — the set of nodes that have been discovered but not yet processed. At each step, BFS removes a node from the front of the queue, processes it, and adds its unvisited neighbors to the back. The ordering of the queue is what enforces the layer-by-layer expansion: neighbors added at one step are processed before the neighbors of neighbors added at the next step.

For the delivery system’s route-finding problem, BFS over an unweighted graph finds the route with fewest hops. The knowledge engine uses the same layering to discover documents: first those directly linked to the query result, then those one hop further.

Traversal Safety: Three Required Controls

A traversal that visits the right nodes in the right order is correct. A traversal without safety controls is correct on graphs that cooperate and incorrect on graphs that do not.

Visited tracking is the first required control, and it is not optional for any graph that may contain cycles. A traversal that does not record which nodes have been visited will follow a cycle indefinitely, revisiting the same nodes without making progress. The visited set — introduced in Thinking Recursively for recursive DFS — is equally necessary for iterative BFS. Every node is added to the visited set at the moment it is first discovered, before it is processed, so that subsequent encounters with the same node are recognized and skipped.

Depth and expansion bounds are the second required control for traversals that must be bounded. A BFS over a document graph with no depth limit will explore the entire connected component of the starting node, which may be the entire document collection. A depth limit of two means: visit the start node and its direct neighbors (depth one) and their neighbors (depth two), then stop. The bound must be enforced explicitly — it does not emerge automatically from the traversal structure — and it must be chosen based on what the system needs to compute, not on what happens to work in testing.

Deterministic ordering is the third required control for traversals whose callers depend on output order. The order in which a node’s neighbors are processed during traversal may depend on the order in which they appear in the adjacency structure — and, ultimately, on when entities were created. A traversal that produces different output on different runs, or different output on different machines, is not a correct implementation of a deterministic algorithm — it is an algorithm whose correctness depends on an assumption it never stated. When the traversal’s output order is meaningful, the ordering must be declared explicitly and enforced.

From Requirement to Traversal Design

Consider the requirement:

“From a starting document, discover connected documents up to depth two.”

Step 1: Define the reachability scope. Depth two means: the start document, the documents directly linked to it (depth one), and the documents linked from those (depth two). Documents at depth three or beyond are outside scope. The depth limit is a correctness constraint, not a performance optimization — the result at depth two is not a subset of the result at depth three; it is a different, defined output.

Step 2: Choose the traversal. BFS is the right choice because the requirement is organized by depth layer. BFS naturally produces depth-one results before depth-two results, which matches the structure of the output. DFS would find documents at varying depths in an order that depends on the graph’s shape, not on the depth criterion. The choice of BFS is a correctness decision.

Step 3: Define the duplicate policy. Each document is visited at most once. If document D is reachable from the start through two different paths — one of length one and one of length two — it appears in the output once, at the depth it was first reached. This policy is enforced by the visited set.

Step 4: Define the output semantics. The output is the sequence of discovered document identifiers in the order they were first reached: the start document, then its neighbors in the order they appear in the adjacency structure, then their unvisited neighbors in order. The visit order must be deterministic.

Step 5: Define failure behavior. An unknown start identifier produces INVALID_START. A start document with no outgoing links produces a result containing only the start document itself with status ISOLATED. Both cases are declared outcomes.

A Traversal in Code

class Explore_Result
create
  make(status, discovered: String) do
    this.status := status
    this.discovered := discovered
  end
feature
  status: String
  discovered: String
invariant
  valid_status:
    status = "OK" or
    status = "ISOLATED" or
    status = "INVALID_START"
end

class Graph_Explorer
feature
  -- Document -> documents it links to, in a fixed order.
  links: Map[String, Array[String]]

  explore(start: String, max_depth: Integer): Explore_Result
  require
    start_present: start /= ""
    depth_valid: max_depth >= 0
  do
    if not links.contains_key(start) then
      result := create Explore_Result.make("INVALID_START", "")
    elseif links.get(start).is_empty then
      result := create Explore_Result.make("ISOLATED", start)
    else
      -- depth doubles as the visited set; order is 
      -- both the BFS queue and the discovery order.
      let depth: Map[String, Integer] := {}
      depth.put(start, 0)
      let order: Array[String] := [start]
      from let i := 0 until i >= order.length do
        let doc := order.get(i)
        if depth.get(doc) < max_depth then
          across links.try_get(doc, []) as next do
            if not depth.contains_key(next) then
              depth.put(next, depth.get(doc) + 1)
              order.add(next)
            end
          end
        end
        i := i + 1
      end
      let discovered := start
      from let k := 1 until k >= order.length do
        discovered := discovered + "," + order.get(k)
        k := k + 1
      end
      result := create Explore_Result.make("OK", discovered)
    end
  ensure
    declared_status:
      result.status = "OK" or
      result.status = "ISOLATED" or
      result.status = "INVALID_START"
  end

create
  make(links: Map[String, Array[String]]) do
    this.links := links
  end
end

The structure of explore encodes the five design decisions from the worked path. The depth limit from Step 1 is a parameter, and a document is expanded only while its depth is below the limit, so documents at depth three are discovered by nothing when the limit is two. The traversal from Step 2 is breadth-first: order serves as the queue, consumed from the front, so every document at depth one is discovered before any document at depth two. The duplicate policy from Step 3 is the depth map, which doubles as the visited set — a document reached a second time, by a longer path or around a cycle, is already in it and is ignored. Because order records documents in the order they were first reached, it is also the output from Step 4, and because each document’s links are visited in the order the map stores them, that output is deterministic. The two failure outcomes from Step 5, INVALID_START and ISOLATED, are checked before the traversal begins.

The adjacency map links is the explicit representation of the graph’s structure. The traversal consults it directly rather than inferring connectivity from its own control flow. This is the same separation established in Graphs — Networks of Everything: the graph structure and the traversal algorithm are distinct, and the traversal’s correctness depends only on what the adjacency structure reports, not on how it is stored.

With links A → B, A → C, B → D, and C → D, exploring from A to depth two yields A,B,C,D: both depth-one documents before the depth-two document, and D once, although two paths reach it. To depth one, the same call yields A,B,C. Those two results are worth turning into tests, because they are exactly the properties the requirement states — layer order and no duplicates — and a traversal that violated either would still return a plausible-looking list.

The Question Decides the Traversal

The delivery system shows most plainly that the traversal follows the question, not the graph. DFS over the road graph explores every location reachable from a starting point, which answers whether a destination is reachable at all and enumerates alternate routes when the primary one is blocked. BFS over the same graph finds the route with the fewest hops. The graph is the same; the question decides the traversal.

The knowledge engine uses BFS to discover related documents in layers — those cited directly by a result, then those cited by them — up to a depth limit that stops the traversal from expanding to the whole collection when connectivity is dense. The virtual world uses both: DFS over the containment hierarchy visits every object in a zone before moving to the next, which suits operations that aggregate over a scope, while BFS over the interaction graph finds entities within a given number of interaction hops, for effects that propagate through chains of interactions.

Where Traversal Design Fails

No visited policy. A traversal without a visited set will follow cycles indefinitely. This is a latent bug in any codebase that uses traversal over graphs that may contain cycles — which includes every real-world graph. The visited set is mandatory. Omitting it because the current test graphs happen to be acyclic is not a defense; the first cyclic graph the traversal encounters will expose the missing control.

Wrong traversal for the objective. DFS used to find a shortest path will find a path, not necessarily the shortest one. BFS used for exhaustive structure exploration in a deep graph will require a large frontier queue before reaching deep nodes. The traversal algorithm must match the objective, and the objective must be stated before the algorithm is chosen. A team that always uses DFS because it is easy to write recursively, or always uses BFS because it feels safer, is making the choice before asking the question.

Implicit or absent bounds. A traversal with no depth or expansion limit will process the entire reachable component of the starting node. For a knowledge engine document graph where any document may be linked to any other, this can mean processing the entire collection. For a delivery network where the graph is fully connected, this means processing every location. Bounds must be chosen deliberately based on what the computation needs, not omitted because the test graphs are small. When a bound is required, its value must be visible in the design — a configurable parameter or a named constant — not buried in a loop condition.

The next chapter, Finding the Best Path, builds on traversal to address a more demanding question: not just which nodes are reachable, but which path to a destination is best by some defined criterion. Path optimization requires both traversal and a cost model, and the interplay between the two determines which algorithms are applicable and what guarantees they can provide.