Depth-Limited search (DLS) is an algorithm for traversing or searching tree or graph data structures. It’s actually specific type of DFS where the search is limited to some depth from start node (root). One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible (within some limit) along each branch before backtracking.

Complexity

  • Time: worst $O(b^l))$
  • Space: worst $O(b\cdot\,l))$
  • Notes:
    • $b$ is branching factor, for example binary tree has branching factor $2$
    • $l$ is limit that we define

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

    const G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
  [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
];

// This is a sample DLS applications where
// we try to find number of descendant of root within some depth
function DLSCount(limit, node, parent) { // node = current node, parent = previous node
  
  let child = 0;
  if (limit > 0) { // cut off the search
    for (let i = 0; i < G[node].length; i++) {
      if (G[node][i]) { // if current node has the i-th node as a child
        child += 1 + DLSCount(limit - 1, i, node); // recursively call DLS
      }
    }
    return child;
  }
  return child;
}

console.log(`Number of descendant is ${DLSCount(2, 0)}`);