Breadth-First Search (BFS) is a graph traversal algorithm used to explore and visit all the vertices of a graph in a breadthward motion, i.e., it explores all the neighbors of a vertex before moving on to their neighbors. BFS is often used to find the shortest path in an unweighted graph, among other applications.
Here's how BFS works, along with an example:
1. Start at a source vertex.
2. Initialize a queue (FIFO) data structure and enqueue the source vertex.
3. Mark the source vertex as visited to avoid revisiting it.
4. Repeat the following steps until the queue is empty:
a. Dequeue the front vertex from the queue.
b. Process (print, store, or perform some other operation) the dequeued vertex.
c. Enqueue all unvisited neighbors of the dequeued vertex.
d. Mark the neighbors as visited.
Let's illustrate BFS with a simple example:
Consider the following undirected graph:
```
A
/ \
B C
/ / \
D E F
```
Starting from vertex A, we perform BFS:
1. Start at vertex A.
2. Enqueue A: Queue = [A]
3. Mark A as visited.
4. Dequeue A, process A.
5. Enqueue B and C (neighbors of A): Queue = [B, C]
6. Mark B and C as visited.
Now, the queue contains [B, C].
7. Dequeue B, process B.
8. Enqueue D (neighbor of B): Queue = [C, D]
9. Mark D as visited.
Now, the queue contains [C, D].
10. Dequeue C, process C.
11. Enqueue E and F (neighbors of C): Queue = [D, E, F]
12. Mark E and F as visited.
Now, the queue contains [D, E, F].
13. Dequeue D, process D.
14. The queue is now [E, F].
15. Dequeue E, process E.
16. The queue is now [F].
17. Dequeue F, process F.
18. The queue is now empty.
BFS has visited all the vertices in the graph. The order in which it visited the vertices is: A, B, C, D, E, F.
BFS guarantees that it will visit all vertices at the current level before moving to the next level, which is why it is used for finding shortest paths in unweighted graphs. In this example, BFS would give you the shortest path from vertex A to any other vertex in the graph.
CODE:
#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 5 // Adjust this to the number of nodes in your graph
int graph[MAX_NODES][MAX_NODES]; // Adjacency matrix
bool visited[MAX_NODES]; // Array to keep track of visited nodes
// Queue implementation
int queue[MAX_NODES];
int front = -1;
int rear = -1;
void enqueue(int node) {
if (rear == MAX_NODES - 1) {
printf("Queue is full.\n");
} else {
if (front == -1) {
front = 0;
}
rear++;
queue[rear] = node;
}
}
int dequeue() {
int node;
if (front == -1) {
printf("Queue is empty.\n");
return -1;
} else {
node = queue[front];
front++;
if (front > rear) {
front = rear = -1;
}
return node;
}
}
bool isQueueEmpty() {
return front == -1;
}
void bfs(int start, int numNodes) {
enqueue(start);
visited[start] = true;
while (!isQueueEmpty()) {
int current = dequeue();
printf("%d ", current);
for (int i = 0; i < numNodes; i++) {
if (graph[current][i] && !visited[i]) {
enqueue(i);
visited[i] = true;
}
}
}
}
int main() {
int numNodes = 5; // Adjust this to the number of nodes in your graph
// Initialize the graph matrix (0-based indexing)
for (int i = 0; i < numNodes; i++) {
visited[i] = false;
for (int j = 0; j < numNodes; j++) {
graph[i][j] = 0;
}
}
// Define the edges of the graph
graph[0][1] = 1;
graph[0][2] = 1;
graph[2][3] = 1;
graph[2][4] = 1;
printf("Breadth-First Search starting from node 0: ");
bfs(0, numNodes);
printf("\n");
return 0;
}
OUTPUT:
Breadth-First Search starting from node 0: 0 1 2 3 4
Process returned 0 (0x0) execution time : 0.030 s
Press any key to continue.
0 Comments