State Space Search : Depth First Search

Depth-first search (DFS) is an algorithm for traversing tree or graph data structures. The algorithm starts at the root node and traverses as far as possible along each branch before backtracking.

A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes

Depth first search algorithm given below treats OPEN like a stack. It adds the new candidates at the head of the list.

 The reason it is called depth first start from the search tree, it selects a node from the OPEN list that is deepest or farthest from the start node. The candidates are inspected in the last-in-first-out order. The way it focus is on the new arrivals first, and consequently its characteristic behaviour is that it dives headlong into the search space. 

Given figure illustrates the search tree as seen by DFS represented by two lists OPEN and CLOSED. The function RemoveSeen removes any nodes that are already on OPEN or CLOSED. 

The function MakePairs takes the nodes returned by RemoveSeen and constructs node  pairs with the parent node, which are then pushed onto OPEN.

The algorithm below shows the DFS here :

DepthFirstSearch ()
   open - ( (start, NIL) )
   closed - ( )
   while not Null (open)
      do nodePair - Head (open)
       node - Head(nodePair)
       if GoalTest (node) = TRUE
             then return ReconstructPath (nodePair, closed)
             else closed - Cons (nodePair, closed)
                 children - MoveGen(node)
                     noLoops - RemoveSeen(children, open, closed)
                     new - MakePairs(noLoops, node )
                     open - Append(new, Tail(open) )
  return "No solution found"

RemoveSeen (nodeList, openList, closedList)
    if Null(nodeList)
        then return ()
           else n - Head(nodeList)
              if (OccursIn(n, openList) OR OccursIn(n, closedList) )
                 then return RemoveSeen(Tail(nodeList), openList, closedList)
                 else return Cons(n, RemoveSeen(Tail(nodeList), openList, closedList)

OccursIn(node, listOfPairs)
  if  Null(listOfPairs)
   then return FALSE
   else if n = Head( Head (listOfPairs)
        then return TRUE
        else return OccursIn ( node, Tail (listOfPairs) )

MakePairs (list, parent, depth)
   if Null(list)
      then return ()
      else return (Cons (MakeList( Head (list), parent, depth+1 ) ),
                          MakePairs (Tail(list), parent, depth) )

Applications Of Depth First Search

1.    For an unweighted graph, traversal of the graph produces the minimum spanning tree and all pair shortest path tree.

2.    Detecting cycle in a graph path.

3.    Finding topological sorting .

4.    To test if a graph is bipartite .

5.    Finding strongly connected components of a graph 

6. Solving Puzzles with only one solution such as mazes

Suppose a given problem

DFS treats OPEN like a stack.

The search tree as formed by DFS for the given problem above is as follows :

  

The search tree derived is as follows .

OPEN	CLOSED
(S, NIL)
AS,   BS,  CS	S , NIL
EA,   BS,   CS	AS,     S,NIL
DE,   GE,  BS,    CS	EA,    AS,    S,NIL
GE,    BS,    CS	DE,   EA,    AS,    S,NIL

The Search tree terminates as when Goal G is picked.

The back Pointers are G-E, E-A, A-S

Sources :

https://en.wikipedia.org/wiki/Depth-first_search

https://www.geeksforgeeks.org/applications-of-depth-first-search/

https://books.google.co.in/books?id=Bcj8AwAAQBAJ&pg=PA37&lpg=PA37&dq=reconstructpath+algorithm&source=bl&ots=hLrJrTF0fg&sig=ACfU3U1Mngd76CMmJ4qqvuTTmc1h-MpgUw&hl=en&sa=X&ved=2ahUKEwiRmZi-2pjhAhXHEHIKHf82CRYQ6AEwCHoECAkQAQ#v=onepage&q=reconstructpath%20algorithm&f=false