More

    [ALGORITHM] DEPTH FIRST SEARCH (DFS) GRAPH ALGORITHM

    Depth First Search (DFS) is a graph traversal algorithm where we scan until we reach the depth (leaf node) through any path and then the next path and so on. Forms of tree traversals such as inorder, preorder and post order are a forms of DFS. 

    Algorithm

    void search (Node root){

      if(root == null)

        return;

      visit(root);

      root.visited = true;

      for each (Node n in root.adjacent){

        if(n.visited ==false)

          search(n);

       }

    }

    Unlike trees, Graphs nodes can have path to any other node even forming cycles. Hence, when working with Graph, we must also check if the node has been already visited to avoid infinite loops. In our DFS algorithm we check this using the visited flag. 

    Usage

    DFS is easiest if we want to visit every node in the graph or every node until we find what we want.

    DFS is not ideal, if we have a large tree and want to quit when we are too far from the original node.

    Recent Articles

    OAUTH – FREQUENTLY ASKED QUESTIONS FOR INTERVIEWS AND SELF EVALUATION

    Why is refresh token needed when you have access token? Access tokens are usually short-lived and refresh tokens are...

    SUMO LOGIC VIDEOS AND TUTORIALS

    Sumo Logic Basics - Part 1 of 2 (link is external) (Sep 29, 2016)Sumo Logic Basics - Part 2 of 2...

    GIT – USEFUL COMMANDS

    Discard all local changes, but save them for possible re-use later:  git stash Discarding local changes...

    DISTRIBUTED COMPUTING – RECORDED LECTURES (BITS)

    Module 1 - INTRODUCTION Recorded Lecture - 1.1 Introduction Part I – Definition

    BOOK REVIEW GUIDELINES FOR COOKBOOKS

    Whenever you add reviews for the book, please follow below rules. Write issues in an excel.Create an excel...

    Related Stories

    Leave A Reply

    Please enter your comment!
    Please enter your name here

    Stay on op - Ge the daily news in your inbox