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

Post a Comment