Breadth First Search And Depth First Search

bfs_and_dfs.md

Breadth First Search

Algorithm for searching graph-like data structures, one level at a time.

---

Step by Step

• Start a queue
• Check current node - if false, mark as visited, continue
• Add all unvisited, connected nodes to queue
• Check one by one like the previous node and repeat

---

---

JS Example

function bfs(value, tree) {

  queue = [];

  queue.unshift(tree);

  while (queue.length > 0) {
    curNode = queue.pop();
    if (curNode.value === value) {
      return curNode;
    }

    var len = curNode.children.length;

    for (var i = 0; i < len; i++) {
      queue.unshift(curNode.children[i]);
    }
  }

  return null;
}

---

Complexity

O(n^2)

---

When to Use

• Solution is not far from the root of the tree
• Tree is very deep and solutions are rare

---

Depth First Search

Algorithm for searching graph-like data structures... aggresively.

---

Step by Step

• Check current node - if found, return node
• For that node find the length of children
• For that length, recursively repeat search

---

---

JS Examples

---

Example One

function dfs(value, node) {

  if (node.value === value) {
    return node;
  }

  var len = node.children.length;

  for (var i = 0; i < len; i++) {
    var foundNode = dfs(value, node.children[i]);
    if (foundNode) {
      return foundNode;
    }
  }
  return null;
}

---

Example Two

function dfs(value, node) {

  stack = [];

  stack.push(node);

  while (stack.length != 0) {
    var curNode = stack.peek()
    if (curNode.value == value) {
      return curNode;
    }
    curNode.visited = true
    stack.push(getFirstUnvistedNode(curNode));
  }

}

---

Complexity

O(n^2)

---

• Much lower memory requirements (compared to BFS)
• Common, usually far from root