Monday, March 21, 2011

Graphs and their applications (Breadth First Search)

This is second article of series: Graphs and graph searching where we'll discuss about simple Breadth First Search (BFS) 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 BFSSearch(i,j). This function is an implementation of Breadth first search where the search algorithm begins at root node and explores all neighbouring nodes before going to the next level. Then for each neighbouring nodes, it explores their unexplored neighbour node and so on until it finds the goal.
Here is a simple algorithm



1. Enqueue the root node

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


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


4. Repeat Step 2
Public Function BFSSearch(ByVal startNode As Integer, ByVal endNode As Integer)
        Dim i, n As Integer
        _fringe.Clear() 'Clear the queue, (also called as Open list) 
        _visited.Clear() 'Clear the queue which stores the nodes that have been expanded or visited
        _fringe.Enqueue(startNode)
        While (1)
            If _fringe.Count > 0 Then
                n = _fringe.Dequeue()
                If (n = endNode) Then
                    Return True
                End If
                If Not _visited.Contains(n) Then
                    _visited.Enqueue(n)

                    For i = 0 To _numberOfNodes - 1
                        If (isAdjacent(n, i)) Then
                            _fringe.Enqueue(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 _fringe and _visited to be sure that no data is present from previous search. _fringe contains index to the nodes that are to be expanded or visited and _visited contains index to the nodes that have already been visited.


Here is my program for the following problem of reaching Bucharest from Arad:


Breadth First Search

No comments:

Recent Posts