Depth First Search algorithm

// Depth First Search implementation in purest form

// relationship between nodes
const graph5 = [
  [1, 2], // SFO, index 0
  [0, 2, 3], // ORD, index 1
  [0, 1, 3, 4], // DEN, index 2
  [1, 2, 4], // JFK, index 3
  [2, 3], // IAH, index 4
]

// nodes' information
const idxToAirport = {
  '0': { name: 'SFO' },
  '1': { name: 'ORD' },
  '2': { name: 'DEN' },
  '3': { name: 'JFK' },
  '4': { name: 'IAH' }
}

const depthFirstSearchPure = (initNodeIdx) => {
  const result = []
  const seen = new Set()
  const stack = [initNodeIdx] // REMEMBER to use a proper stack data structure IRL

  console.log('Starting airport: ', idxToAirport[initNodeIdx].name)

  while(stack.length > 0) {

    const curNodeIdx = stack.pop() // pop the stack

    // if we've never seen this node before, process,
    // otherwise, ignore the node
    if(!seen.has(curNodeIdx)) {

      seen.add(curNodeIdx) // add this node to seen list

      const curNodeNeighbors = graph5[curNodeIdx] // get the neighbors

      curNodeNeighbors.forEach(nodeIdx => 
        !seen.has(nodeIdx) && stack.push(nodeIdx)) // push neighbor on top
  
      result.push(idxToAirport[curNodeIdx].name) // save current node to result

      console.log('result: ', result)
    }
  }
}

depthFirstSearchPure(0) // result: [ 'SFO', 'DEN', 'IAH', 'JFK', 'ORD' ]

$ node depth-first-search-pure.js
Starting airport:  SFO
result:  [ 'SFO' ]
result:  [ 'SFO', 'DEN' ]
result:  [ 'SFO', 'DEN', 'IAH' ]
result:  [ 'SFO', 'DEN', 'IAH', 'JFK' ]
result:  [ 'SFO', 'DEN', 'IAH', 'JFK', 'ORD' ]

// Sales path DFS Loop style

// prepare path data
let nodeCount = 1

// Constructor to create a new Node
function Node(cost) {
  this.cost = cost
  this.children = []
  this.id = nodeCount++
}

// 
var root = new Node(0)
root.children.push(new Node(5))
root.children.push(new Node(3))
root.children.push(new Node(6))
root.children[0].children.push(new Node(4))
root.children[1].children.push(new Node(2))
root.children[1].children.push(new Node(0))
root.children[2].children.push(new Node(1))
root.children[2].children.push(new Node(5))
root.children[1].children[0].children.push(new Node(1))
root.children[1].children[1].children.push(new Node(10))
root.children[1].children[0].children[0].children.push(new Node(1))
// console.log(JSON.stringify(root, null, 4))

// done preparing path data

// depth first search on sales path, using WHILE LOOP
const dfsSalesPath = (node) => {
  const seen = new Set()
  const stack = [node] // REMEMBER to use a proper stack data structure IRL
  const path = [] // current path
  const paths = [] // all possible paths

  while(stack.length > 0) {

    printStack(stack)

    const curNode = stack.pop() // pop the stack

    // if we see a separator
    if(curNode === '|') {
      path.pop() // remove parent node from path
      continue // and continue to next node
    } else { // if not
      path.push(curNode.cost) // save current node into path
    }

    // if we've never seen this node before, process,
    // otherwise, ignore the node
    if(!seen.has(curNode.id)) {

      seen.add(curNode.id) // add this node to seen list
      let seenAllChildNodes = true
      let pushedSeparator = false

      curNode.children.forEach(node => {
        if(!seen.has(node.id)) {
          if(pushedSeparator === false) {
            stack.push('|')
            pushedSeparator = true
          }
          stack.push(node) // push neighbor on top
          seenAllChildNodes = false
        }
      })
        

      // pop the current path when we're at a leaf node
      // or all adjacent nodes have been visited
      if (
        curNode.children.length === 0 || // at leaf node
        seenAllChildNodes // or have seen all adjacent nodes
      ) {
        paths.push([
          path.join(','),
          path.reduce((partialSum, cut) =>  partialSum + parseInt(cut), 0)
        ])
        path.pop()
      }

      // console.log("path:", path)
    }
  }

  return paths
}

console.log('all possible paths & costs:', dfsSalesPath(root))


// print node `cost` instead of the whole node object
function printStack (stack) {
  const print = []
  for(let el of stack) {
    if(el === '|') {
      print.push(el)
    } else {
      print.push(el.cost)
    }
  }
  console.log('stack:', print)
}

$ node sales-path-with-loop.js 
stack: [ 0 ]
stack: [ '|', 5, 3, 6 ]
stack: [ '|', 5, 3, '|', 1, 5 ]
stack: [ '|', 5, 3, '|', 1 ]
stack: [ '|', 5, 3, '|' ]
stack: [ '|', 5, 3 ]
stack: [ '|', 5, '|', 2, 0 ]
stack: [ '|', 5, '|', 2, '|', 10 ]
stack: [ '|', 5, '|', 2, '|' ]
stack: [ '|', 5, '|', 2 ]
stack: [ '|', 5, '|', '|', 1 ]
stack: [ '|', 5, '|', '|', '|', 1 ]
stack: [ '|', 5, '|', '|', '|' ]
stack: [ '|', 5, '|', '|' ]
stack: [ '|', 5, '|' ]
stack: [ '|', 5 ]
stack: [ '|', '|', 4 ]
stack: [ '|', '|' ]
stack: [ '|' ]
all possible paths & costs: [
  [ '0,6,5', 11 ],
  [ '0,6,1', 7 ],
  [ '0,3,0,10', 13 ],
  [ '0,3,2,1,1', 7 ],
  [ '0,5,4', 9 ]
]

// Sales path DFS recursion style

// prepare path data
let nodeCount = 1

// Constructor to create a new Node
function Node(cost) {
  this.cost = cost
  this.children = []
  this.id = nodeCount++
}

// 
var root = new Node(0)
root.children.push(new Node(5))
root.children.push(new Node(3))
root.children.push(new Node(6))
root.children[0].children.push(new Node(4))
root.children[1].children.push(new Node(2))
root.children[1].children.push(new Node(0))
root.children[2].children.push(new Node(1))
root.children[2].children.push(new Node(5))
root.children[1].children[0].children.push(new Node(1))
root.children[1].children[1].children.push(new Node(10))
root.children[1].children[0].children[0].children.push(new Node(1))
// console.log(JSON.stringify(root, null, 4))

// done preparing path data

// depth first search on sales path, recursion style
const dfsSalesPathRecursion = (rootNode) => {
  return cost(rootNode)
  
  function cost(node) {
    if(node.children.length == 0) { // base case, aka exit condition
      console.log('leaf cost:', node.cost)
      return node.cost
    } else {
      let costs = new Array(node.children.length)
      for(let i = 0; i < node.children.length; i++) {
        costs[i] = node.cost + cost(node.children[i])
      }
      console.log('min from costs:', costs)
      return Math.min.apply(null, costs)
    }
  }
}

console.log('cheapest path cost:', dfsSalesPathRecursion(root)) // 7

$ node sales-path-bottom-up-recursion.js
leaf cost: 4
min from costs: [ 9 ]
leaf cost: 1
min from costs: [ 2 ]
min from costs: [ 4 ]
leaf cost: 10
min from costs: [ 10 ]
min from costs: [ 7, 13 ]
leaf cost: 1
leaf cost: 5
min from costs: [ 7, 11 ]
min from costs: [ 9, 7, 7 ]
cheapest path cost: 7

// Leetcode #733 Flood fill: https://leetcode.com/problems/flood-fill/description/

// DFS flood fill
 var floodFill = function(image, sr, sc, color) {

  console.log('image:', image)

  const stack = [[sr, sc]] // REMEMBER to use a proper stack data structure IRL
  const seen = new Set()
  
  while(stack.length > 0) {

      // console.log(stack)

      const [curSr, curSc] = stack.pop() // pop the stack
      const curPosStr = '' + curSr + curSc

      // if we never seen this node before, process
      if(!seen.has(curPosStr)) {
          seen.add(curPosStr)

          const floodVal = image[curSr][curSc] // get starting pixel value
          image[curSr][curSc] = color // update starting pixel to `color`

          const neighbors = [ // list of all possible neighbors
              [curSr + 1, curSc],
              [curSr - 1, curSc],
              [curSr, curSc + 1],
              [curSr, curSc - 1],
          ]

          for(let [nSr, nSc] of neighbors) { // for each neighbor
              const nPosStr = '' + nSr + nSc
              if(
                  !seen.has(nPosStr) && // never seen
                  nSr >= 0 && nSr < image.length && // within image width
                  nSc >= 0 && nSc < image[0].length && // within image height
                  image[nSr][nSc] == floodVal // same pixel value with started pixel
              ) {
                  stack.push([nSr, nSc]) // push node on top the stack
              }
          }
      }
  } // otherwise, ignore

  return image
}

const image = [
  [1, 1, 1, 0, 1],
  [1, 1, 1, 0, 1],
  [1, 1, 0, 1, 1],
  [1, 1, 0, 0, 1],
]
const sr = 1
const sc = 1
const color = 2

console.log('flood filled image:', floodFill(image, sr, sc, color))

$ node flood-fill.js
image: [
  [ 1, 1, 1, 0, 1 ],
  [ 1, 1, 1, 0, 1 ],
  [ 1, 1, 0, 1, 1 ],
  [ 1, 1, 0, 0, 1 ]
]
flood filled image: [
  [ 2, 2, 2, 0, 1 ],
  [ 2, 2, 2, 0, 1 ],
  [ 2, 2, 0, 1, 1 ],
  [ 2, 2, 0, 0, 1 ]
]