Tensions in Practice: Shallow discovery in tension with a smaller frontier¶
Graph exploration · seven-node tree
A tree has links S→A and S→B; A leads to C and D, while B leads to E and F. Each link costs one step. Both procedures visit every node, checking it when taken from the waiting frontier. Breadth first processes all nearby nodes before deeper ones. Depth first follows A to a leaf while B waits. The tables show both the visit and the unfinished work it leaves behind.
Find shallow results first
Process nodes in increasing distance from the starting node.
Keep less unfinished breadth
Follow a branch while retaining fewer exposed alternatives in this tree.
Why these aims pull against each other
The frontier is live work, not just a list of final visits. Breadth first peaks at four waiting nodes here; depth first peaks at three, but visits depth two before finishing depth one.
Choose an arrangement to see what changes and what remains difficult.
Finite illustrative comparisons. Text states carry the meaning; color is not a measured score or universal preference.
What this choice protects
What it costs
When it fits
Compare the arrangements
Breadth first
Use a first-in, first-out queue, adding each node’s children left to right.
| Visit | Waiting | Depth | |
|---|---|---|---|
| 1 | S | A, B | 0 |
| 2 | A | B, C, D | 1 |
| 3 | B | C, D, E, F | 1 |
| 4 | C | D, E, F | 2 |
| 5 | D | E, F | 2 |
| 6 | E | F | 2 |
| 7 | F | None | 2 |
- What it protects
- Depth never decreases in this unweighted tree; if B and C both qualify, B is the first processed match and has the shorter path.
- What it costs
- The queue holds C, D, E and F together after B; the peak is four waiting nodes.
- When it fits
- The first match must have minimum unweighted distance, or coverage by layers is the purpose.
Illustration note: The complete trace continues after any hypothetical match. A match is tested on processing, not initial exposure; the tree has no repeated nodes.
Depth first
Use a stack with the left child placed next, preserving the same left-to-right neighbor rule.
| Visit | Waiting | Depth | |
|---|---|---|---|
| 1 | S | A, B | 0 |
| 2 | A | C, D, B | 1 |
| 3 | C | D, B | 2 |
| 4 | D | B | 2 |
| 5 | B | E, F | 1 |
| 6 | E | F | 2 |
| 7 | F | None | 2 |
- What it protects
- A leaf is processed earlier, and this trace needs at most three waiting nodes.
- What it costs
- If B and C both qualify, C is processed first even though B has the shorter path.
- When it fits
- Deep branch inspection or reduced frontier storage matters more than a shortest-depth first result.
Illustration note: The counts concern the displayed frontier only, not total memory or a universal ratio. A visited set and other implementation state can add storage.
What this illustration does—and does not—establish
Network Traversal: Breadth versus depth supplies the breadth/depth conflict. The finite tree, queues and optional qualifying nodes are editorial and directly enumerated.
- Shortest depth means fewest edges in this unweighted graph; weighted costs need a different policy.
- Both arrangements exhaust the same finite tree. Neither changes connectivity or authorizes a visit.
- The memory comparison is for this explicit tree and frontier representation, not all networks.
Source entries
Network Traversal
Network Traversal: Breadth versus depth supplies the conflict examined here.
Breadth versus depth
T3 — Breadth versus depth. Breadth-first policies reveal nearby coverage and shortest unweighted distances but consume a large frontier; depth-first policies use less frontier memory and expose long chains quickly but can spend the budget inside one branch. Diagnostic: match the frontier policy to the result being claimed rather than treating visit order as neutral.