Depth-First Search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Applications

• Finding connected components.
• Topological sorting.
• Finding 2-(edge or vertex)-connected components.
• Finding 3-(edge or vertex)-connected components.
• Finding the bridges of a graph.
• Generating words in order to plot the Limit Set of a Group.
• Finding strongly connected components.
• Planarity testing
• Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)
• Maze generation may use a randomized depth-first search.
• Finding biconnectivity in graphs.

References

• trekhleb/javascript-algorithms
• Wikipedia
• Tree Traversals (Inorder, Preorder and Postorder)
• BFS vs DFS

Implementations

• Python

• 1
  # TODO: Implement in Python
  

JavaScript

• leastSignificantDigit
• bottomUp
• topDown
• Graph
• Shortest Path
• Tree
• Weighted Graph

• 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
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  console.log(`original array = [${D[0].join(', ')}]`);
  
  function pow(base, expo) {
    let ans = 1;
    for (let i = 0; i < expo; i++) {
      ans *= base;
    }
    return ans;
  }
  
  function digit(i, exp) {
    return parseInt(D[0][i] / pow(10, exp) % 10);
  }
  
  for (let exp = 0; exp < 3; exp++) {
    
    console.log(`Digit: ${exp}`);
    
    let i;
    for (i = 0; i < D[0].length; i++) {
      const d = digit(i, exp);
      
      D[2][d] += 1;
      
    }
    for (i = 1; i < 10; i++) {
      
      D[2][i] += D[2][i - 1];
      
    }
    for (i = D[0].length - 1; i >= 0; i--) {
      const d = digit(i, exp);
      
      D[2][d] -= 1;
      
      D[1][D[2][d]] = D[0][i];
      
    }
    for (i = 0; i < D[0].length; i++) {
      
      D[0][i] = D[1][i];
      
    }
    for (i = 0; i < 10; i++) {
      D[2][i] = 0;
      
    }
  }
  
  console.log(`sorted array = [${D[0].join(', ')}]`);
  

• 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
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  console.log(`original array = [${D[0].join(', ')}]`);
  
  function mergeSort(start, end) {
    if (Math.abs(end - start) <= 1) return;
  
    let mergeFrom = 0;
    let mergeTo = 1;
    let width;
    let i;
    for (width = 1; width < end; width *= 2) {
      
      for (i = 0; i < end; i += 2 * width) {
        merge(mergeFrom, i, Math.min(i + width, end), Math.min(i + 2 * width, end), mergeTo);
      }
      // this could be copy(mergeTo, mergeFrom, start, end);
      // but it is more effecient to swap the input arrays
      // if you did copy here, you wouldn't need the copy at the end
      mergeFrom = (mergeFrom === 0 ? 1 : 0);
      mergeTo = 1 - mergeFrom;
    }
    if (mergeFrom !== 0) {
      
      copy(mergeFrom, mergeTo, start, end);
    }
  }
  
  function merge(mergeFrom, start, middle, end, mergeTo) {
    let i = start;
    let j = middle;
    let k;
    // in an actual merge implementation, mergeFrom and mergeTo would be arrays
    // here for the ability to trace what is going on better, the arrays are D[mergeFrom] and D[mergeTo]
  
    for (k = start; k < end; k++) {
  
      if (i < middle && (j >= end || D[mergeFrom][i] <= D[mergeFrom][j])) {
  
        D[mergeTo][k] = D[mergeFrom][i];
        i += 1;
      } else {
  
        D[mergeTo][k] = D[mergeFrom][j];
        j += 1;
      }
    }
  }
  
  function copy(mergeFrom, mergeTo, start, end) {
    let i;
    for (i = start; i < end; i++) {
  
      D[mergeTo][i] = D[mergeFrom][i];
  
    }
  }
  
  mergeSort(0, D[0].length);
  
  console.log(`sorted array = [${D[0].join(', ')}]`);
  

• 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
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  console.log(`original array = [${D.join(', ')}]`);
  
  function mergeSort(start, end) {
    if (Math.abs(end - start) <= 1) return [];
    const middle = Math.ceil((start + end) / 2);
  
    mergeSort(start, middle);
    mergeSort(middle, end);
  
    console.log(`divide left[${start}, ${middle - 1}], right[${middle}, ${end - 1}]`);
    
    return mergeSort.merge(start, middle, end);
  }
  
  mergeSort.merge = (start, middle, end) => {
    const leftSize = middle - start;
    const rightSize = end - middle;
    const maxSize = Math.max(leftSize, rightSize);
    const size = end - start;
    const left = [];
    const right = [];
    let i;
  
    for (i = 0; i < maxSize; i++) {
      if (i < leftSize) {
        left.push(D[start + i]);
        
      }
      if (i < rightSize) {
        right.push(D[middle + i]);
        
      }
    }
    
    console.log(`left array = [${left.join(', ')}], ` + `right array = [${right.join(', ')}]`);
  
    i = 0;
    while (i < size) {
      if (left[0] && right[0]) {
        if (left[0] > right[0]) {
          D[start + i] = right.shift();
          
          console.log(`rewrite from right array[${i}] = ${D[start + i]}`);
          
        } else {
          D[start + i] = left.shift();
          
          console.log(`rewrite from left array[${i}] = ${D[start + i]}`);
          
        }
      } else if (left[0]) {
        D[start + i] = left.shift();
        
        console.log(`rewrite from left array[${i}] = ${D[start + i]}`);
        
      } else {
        D[start + i] = right.shift();
        
        console.log(`rewrite from right array[${i}] = ${D[start + i]}`);
        
      }
  
      i++;
    }
  
    const tempArray = [];
    for (i = start; i < end; i++) tempArray.push(D[i]);
    
    console.log(`merged array = [${tempArray.join(', ')}]`);
    
  };
  
  mergeSort(0, D.length);
  
  console.log(`sorted array = [${D.join(', ')}]`);
  

• 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
  32
  33
  34
  35
  36
  37
  38
  39
  function DFSExplore(graph, source) {
    const stack = [[source, null]];
    const visited = [];
    let node;
    let prev;
    let i;
    let temp;
    for (i = 0; i < graph.length; i++) {
      visited.push(false);
    }
  
    while (stack.length > 0) {
      temp = stack.pop();
      node = temp[0];
      prev = temp[1];
  
      if (!visited[node]) {
        visited[node] = true;
  
        for (i = 0; i < graph.length; i++) {
          if (graph[node][i]) {
            stack.push([i, node]);
          }
        }
      }
    }
  
    return visited;
  }
  
  const visited = DFSExplore(G, 0);
  let check = true;
  for (let i = 0; i < visited.length; i++) check &= visited[i];
  
  if (check) {
    console.log('The Graph is CONNECTED');
  } else {
    console.log('The Graph is NOT CONNECTED');
  }
  

• 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
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  function DFS(node, parent, weight) { // node = current node, parent = previous node
    if (minWeight < weight) return;
    if (node === e) {
      
      if (minWeight > weight) {
        minWeight = weight;
      }
      
      return;
    }
    D[node] = true; // label current node as discovered
    
    for (let i = 0; i < G[node].length; i++) {
      if (G[node][i]) { // if the path from current node to the i-th node exists
        if (!D[i]) { // if the i-th node is not labeled as discovered
          DFS(i, node, weight + G[node][i]); // recursively call DFS
        }
      }
    }
    D[node] = false; // label current node as undiscovered
    
  }
  
  const s = Randomize.Integer({ min: 0, max: G.length - 1 }); // s = start node
  let e; // e = end node
  do {
    e = Randomize.Integer({ min: 0, max: G.length - 1 });
  } while (s === e);
  const MAX_VALUE = Infinity;
  let minWeight = MAX_VALUE;
  
  console.log(`finding the shortest path from ${s} to ${e}`);
  
  let D = []; // D[i] indicates whether the i-th node is discovered or not
  for (let i = 0; i < G.length; i++) D.push(false);
  DFS(s, undefined, 0);
  
  if (minWeight === MAX_VALUE) {
    console.log(`there is no path from ${s} to ${e}`);
  } else {
    console.log(`the shortest path from ${s} to ${e} is ${minWeight}`);
  }
  

• 1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  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],
  ];
  
  function DFS(node, parent) { // node = current node, parent = previous node
    
    for (let i = 0; i < G[node].length; i++) {
      if (G[node][i]) { // if current node has the i-th node as a child
        DFS(i, node); // recursively call DFS
      }
    }
  }
  
  DFS(0);
  

• 1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  let D; // D[i] indicates whether the i-th node is discovered or not
  
  function DFS(node, parent, weight) { // node = current node, parent = previous node
    
    D[node] = true; // label current node as discovered
    for (let i = 0; i < G[node].length; i++) {
      if (G[node][i]) { // if the edge from current node to the i-th node exists
        if (!D[i]) { // if the i-th node is not labeled as discovered
          DFS(i, node, weight + G[node][i]); // recursively call DFS
        }
      }
    }
    D[node] = false; // label current node as undiscovered
    
  }
  
  for (let i = 0; i < G.length; i++) { // start from every node
    
    console.log(`start from ${i}`);
    
    D = [];
    for (let j = 0; j < G.length; j++) D.push(false);
    DFS(i, undefined, 0);
  }