15.00 - Breadth First and Depth First Searches - Teradata Database

Teradata Database SQL Data Definition Language Detailed Topics

Product
Teradata Database
Release Number
15.00
Content Type
Programming Reference
Publication ID
B035-1184-015K
Language
English (United States)

Breadth First and Depth First Searches

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

See “Breadth First Reporting” on page 503.

DFS

Depth first search

See “Depth First Reporting” on page 504.

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 (see “Breadth First Reporting” on page 503 and “Depth First Reporting” on page 504).