**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 NextThis 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:

Post a Comment