• Main Menu
  • Depth First Search Algorithm


    A DFS algorithm, as the name implies, is used to search deeper in the graph, whenever possible. The edges are explored, out of the most recently discovered vertex v that still has unexplored edges leaving it. When all of v's edges have been explored, the search backtracks to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the source vertex. DFS uses stack structure to maintain the order in which the vertices are to be processed.

    Algorithm:

    Step 1: Initialize all nodes to ready state (status = 1)

    Step 2: Push the starting node in stack and change its status to the waiting state (status = 2)

    Step 3: Repeat step 4 and 5 until stack is empty

    Step 4: pop the top node n of stack. Process n and change the status of n to the processed state (status = 3)

    Step 5: Push on to the stack, all the neighbor of n that are in ready state (status = 1), and change their status to the waiting state (status = 2) [End of the step 3 loop]

    Step 6: exit

    Output:

    Got Something To Say:

    Your email address will not be published. Required fields are marked *

    3 comments
    1. shamae

      18 October, 2011 at 1:57 am

      it was a good algorithm though i wasn’t understand it enough , it should be clarified correctly and explain it words for words… please have a dev c++ and java..(can u)

      Reply
    2. sibin

      4 May, 2011 at 1:24 pm

      very bad algorithm.
      please modify it.
      9846388009……….

      Reply
    3. seda

      5 February, 2011 at 6:11 am

      it is very good that alogrithem but iwant cod c++
      and steps of that alogrithem

      Reply
    C
    178 queries in 1.107 seconds.