Tuesday, March 22, 2011

Gaphs and their applications (Depth First Search)

This is third article of series: Graphs and graph searching where we'll discuss about simple Depth First Search (DFS) algorithm.

We made a graph class that can represent a graph in the previous article of this series. Lets add another function to this class DFSSearch(i,j). This function is an implementation of Depth first search where the search algorithm begins at root node and explores the first successor of the node then again its first successor and so on until it finds the goal or it reaches the leaf node (i.e nodes without any successors). Then the search backs off to the previous node which is still to be expanded and so on. The algorithm of DFS is similar to that of BFS but the only difference is the use of Stack instead of Queue.
Here is a simple algorithm

1. Push the root node

2. Pop a node-->
If this node is goal node then quit search and return a result
else, push any successors that have not yet been discovered


3. If stack is empty then quit the search because all nodes in the graph has been examined


4. Repeat Step 2
Public Function DFSSearch(ByVal startNode As Integer, ByVal endNode As Integer)
        Dim i, n As Integer
        _visited.Clear()
        _stack.Clear()
        _stack.Push(startNode)
        While (1)
            If _stack.Count > 0 Then
                n = _stack.Pop
                If (n = endNode) Then
                    Return True
                End If
                If Not _visited.Contains(n) Then
                    _visited.Enqueue(n)

                    For i = _numberOfNodes - 1 To 0 Step -1
                        If isAdjacent(n, i) Then
                            _stack.Push(i)
                        End If
                    Next
                End If
            Else
                Exit While
                Return False
            End If

        End While
        Return False
    End Function

Here, index to startNode and endNode is given as input to this function. Rest of the code is pretty straightforward.

But let me explain some of it. First we cleared _stack and _visited to be sure that no data is present from previous search. _stack contains index to the nodes that are to be expanded or visited and _visited contains index to the nodes that have already been visited.

Notice the loop



For i = _numberOfNodes - 1 To 0 Step -1
                        If isAdjacent(n, i) Then
                            _stack.Push(i)
                        End If
                    Next
This is because a stack is LIFO list and we need to traverse a graph in Left to Right order.

Here is my program for going from Arad ( node 0 ) to Bucharest ( node 7 ):




Depth First Search

No comments:

Recent Posts