Hierarchical trees can be traversed either breadth first or depth first. These searches are abbreviated as indicated by the following table.
| Abbreviation | Definition |
|---|---|
| BFS | Breadth first search |
| DFS | Depth first search |
In a BFS, each immediate child of a node is visited before any of its grandchildren.
In a DFS, all descendants of each immediate node in the graph are visited before visiting other immediate children of that node.
Consider the following graph of a parts hierarchy.
If this graph is searched breadth first, its nodes are visited in the following order.
p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12
In contrast, if the graph is searched depth first, its nodes are visited in the following order.
p1 p2 p5 p6 p7 p3 p8 p9 p4 p10 p11 p12
The real effect of specifying a BFS versus a DFS is the ordering of the result set. As a result, it is simple to simulate a BFS or a DFS by simple ordering of the output.