Skip to content

Instantly share code, notes, and snippets.

@chrisco
Forked from bertoort/bfs_and_dfs.md
Created August 31, 2016 21:00
Show Gist options
  • Star 8 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save chrisco/ae1ba58b9df4f92e1db6c3adf39b71b0 to your computer and use it in GitHub Desktop.
Save chrisco/ae1ba58b9df4f92e1db6c3adf39b71b0 to your computer and use it in GitHub Desktop.
Breadth First Search And Depth First Search

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

bfs


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

bfs


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
@iamabs2001
Copy link

Do you have proper implementation ? with a example treee ?

@trafium
Copy link

trafium commented Jan 18, 2022

Both BFS and DFS are O(n) time complexity.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment