Breadth first search (BFS)
In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. Compare BFS with the equivalent, but more memory-efficient Iterative deepening depth-first search and contrast with depth-first search.
BFS was invented in the late 1950s by E. F. Moore and initially used to find the shortest path out of a maze
Algorithm of BFS
The algorithm uses a queue data structure to store intermediate results as it traverses the graph, as follows:
- Enqueue the root node
- Dequeue a node and examine it
- If the element sought is found in this node, quit the search and return a result.
- Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
- If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
- If the queue is not empty, repeat from Step 2.
Pseudocode
Input: A graph G and a root v of G
1 procedure BFS(G,v) is 2 create a queue Q 3 create a set V 4 add v to V 5 enqueue v onto Q 6 while Q is not empty loop 7 t ← Q.dequeue() 8 if t is what we are looking for then 9 return t 10 end if 11 for all edges e in G.adjacentEdges(t) loop 12 u ← G.adjacentVertex(t,e) 13 if u is not in V then 14 add u to V 15 enqueue u onto Q 16 end if 17 end loop 18 end loop 19 return none 20 end BFS
C Language code
/*
Program bfs.c to traverse a graph that uses adjacency
matrix as input and carries out breadth first search
non-recursive method. Uses queue data structure
*/
#include <stdio.h>
#include <conio.h>
#define MAXSIZE 20
struct queueType
{
int items[MAXSIZE];
int front;
int rear;
} queue;
void queueInsert(struct queueType *,int);
int queueDelete(struct queueType *);
int empty(struct queueType *);
void displayQueue(struct queueType *);
void adjMatrix(int[MAXSIZE][MAXSIZE], int);
void BFS(int[MAXSIZE][MAXSIZE], int, int);
void main()
{
int aMat[MAXSIZE][MAXSIZE], startNode, noVertices;
queue.front = -1;
queue.rear = -1; /* Initialize queue to empty */
clrscr();
printf("Enter number of vertices in graph : ");
scanf("%d", &noVertices);
adjMatrix(aMat, noVertices);
printf("Enter start vertex [1 to %d]\n", noVertices);
scanf("%d", &startNode);
printf("\n\n");
BFS(aMat, startNode, noVertices);
printf("\n\n");
displayQueue(&queue);
getch();
}
/* Input function */
void adjMatrix(int aMat[MAXSIZE][MAXSIZE], int no)
{
int i, j;
printf("Input adjacency matrix of order %dx%d\n\n", no, no);
for (i=1; i<=no; i++)
{
printf("Row %d : ", i);
for (j=1; j<=no; j++)
scanf("%d", &aMat[i][j]);
}
printf("\n\n");
}
void BFS(int aMat[MAXSIZE][MAXSIZE], int startNode, int noVertices)
{
int i, j, visited[MAXSIZE], node;
for (i=1; i<=noVertices; i++)
visited[i]=0;
node = startNode ;
visited[node] = 1;
printf("BFS traversal sequence = \n");
while (1)
{
printf(" %d ", node);
for (j=1; j<=noVertices; j++)
{
if ((aMat[node][j] == 1) && (visited[j] == 0))
{
queueInsert(&queue, j);
visited[j] = 1;
}
}
if (empty(&queue))
{
printf("\n\n");
return;
}
else
{
node = queueDelete(&queue);
}
}
}
void queueInsert(struct queueType *queue, int x)
{
/*check for queue full, if so give a warning message and return */
if (queue->rear == MAXSIZE-1)
{
printf("Queue full\n");
return;
} else
{
/* check for queue empty, if so initialized front and rear pointer to zero.
Otherwise increment rear pointer*/
if (queue->front == -1)
{
queue->front = 0;
queue->rear = 0;
} else
{
queue->rear = queue->rear+1;
}
queue->items[queue->rear] = x;
}
}
int queueDelete(struct queueType *queue)
{
int x;
x = queue->items[queue->front];
/* if both pointer at the same position then reset the queue to empty position
otherwise increment front pointer by 1.*/
if (queue->front == queue->rear)
{
queue->front = -1;
queue->rear = -1;
} else
queue->front = queue->front +1 ;
return x;
}
int empty(struct queueType *queue)
{
if (queue->front == -1)
return 1;
else
return 0;
}
void displayQueue(struct queueType *queue)
{
int i=queue->front;
while (i <= queue->rear)
{
printf("%d ", queue->items[i]);
i++;
}
printf("\n");
}
No comments:
Post a Comment