depth-first-search.md

DFS

A depth first search algorithm is a search algorithm majorly used in graph and trees, we can start seraching from any node (say it root node) and go deep down along the path, backtrack if not found and the seraching continues until we found the that node.

In dfs we select one child and traverse the complete child tree before moving to next child of the node.
Note** Traversing only non visited node (if current node is already been visited then move to next node since we must had done dfs on that node so no need to traverse again).

Sequence diagram

step 1 -> if current_node is already been visited then just return otherwise traverse over the childrens of current_node->childs
step 2 -> do dfs one-by-one on each child

Example

let's say we have a tree of 8 nodes, where node 1 is the root.

Now we want to search a node with a value as 8 using dfs (depth first search), start with the root node

depth-first-search.mp4

sudo code

• I always use vector <vector <int>> node(N) for nodes, node[i] stores the list of nodes connected with the edge with ith node, you are free to use anything 🙂.

void dfs(int current_node, int parent) {
  for (int child : node[current_node]) {
    if (child == parent) {
      continue ;
    }
    dfs(child, current_node);
  }
}