Breadth-First/Depth-First Searches & Reporting | VantageCloud Lake - Breadth-First and Depth-First Searches - Teradata Vantage

Breadth First Reporting

You can simulate a BFS result by ordering the final result by the depth of the recursion. For example, consider the following view definition.

    CREATE RECURSIVE VIEW reachable_from (destin, cost, depth) AS (
      SELECT root.destin, root.cost, 0 AS depth
      FROM flights AS root
      WHERE root.source = 'paris'
    UNION ALL
      SELECT result.destin, seed.cost+result.cost, seed.depth+1 AS depth
      FROM reachable_from AS seed, flights AS result
      WHERE seed.destin = result.source
      AND   depth <= 20);

By ordering the query result on the depth variable, the following SELECT request provides a breadth first report on this view.

    SELECT *
    FROM reachable_from
    ORDER BY depth;

Depth First Reporting

You can simulate a DFS result by ordering the final result by the path of the recursion. The path in this context means how a row is found through recursive iterations. In this example, the path is the concatenation of the city names.

    CREATE RECURSIVE VIEW reachable_from (destin,cost,depth,path) AS (
      SELECT root.destin, root.cost, 0 AS depth, destin AS path
      FROM flights AS root
      WHERE root.source = 'paris'
    UNION ALL
      SELECT result.destin,seed.cost+result.cost,seed.depth+1 AS depth,
         seed.path||' '||result.destin
      FROM reachable_from AS seed, flights AS result
      WHERE seed.destin = result.source
      AND   depth <= 20);

    SELECT *
    FROM reachable_from
    ORDER BY path;

Comparison of Using BFS versus DFS

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 instead of a DFS is the ordering of the result set. Therefore, it is simple to simulate a BFS or a DFS by simple ordering of the output.