Algorithm
Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph level by level. It starts at the source node and explores all its neighbors before moving on to the next level of neighbors. BFS is commonly used to find the shortest path in an unweighted graph and is also useful for various other applications.
Here's a high-level description of the BFS algorithm:
-
Initialization:
- Enqueue the source node into a queue.
- Mark the source node as visited.
-
Exploration:
- While the queue is not empty:
- Dequeue a node from the front of the queue.
- Explore all unvisited neighbors of the dequeued node.
- Enqueue each unvisited neighbor into the queue and mark it as visited.
- While the queue is not empty:
-
Termination:
- Repeat step 2 until the queue is empty.
BFS is often implemented using a queue data structure. The order in which nodes are visited is important, as it ensures that nodes closer to the source are visited before nodes farther away. This leads to finding the shortest path in an unweighted graph.
Code Examples
#1 Breadth first search implement in Python
Code -
Python Programming
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
# Example usage:
# Define an adjacency list representation of a graph
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['B', 'H'],
'F': ['C'],
'G': ['C'],
'H': ['E']
}
# Start BFS from the 'A' vertex
print("BFS starting from 'A':")
bfs(graph, 'A')
#2 Breadth first search implement in Java
Code -
Java Programming
import java.util.LinkedList;
import java.util.Queue;
public class BFSExample {
static class Graph {
private int V; // Number of vertices
private LinkedList < Integer>[] adj; // Adjacency list
// Constructor
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList<>();
}
}
// Add an edge to the graph
void addEdge(int v, int w) {
adj[v].add(w);
}
// Breadth-First Search starting from a given source vertex
void BFS(int s) {
// Mark all the vertices as not visited
boolean[] visited = new boolean[V];
// Create a queue for BFS
Queue < Integer> queue = new LinkedList<>();
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.add(s);
while (!queue.isEmpty()) {
// Dequeue a vertex from the queue and print it
s = queue.poll();
System.out.print(s + " ");
// Get all adjacent vertices of the dequeued vertex s
// If an adjacent vertex has not been visited, mark it visited and enqueue it
for (Integer neighbor : adj[s]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
}
public static void main(String[] args) {
// Create a sample graph
Graph graph = new Graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
System.out.println("Breadth First Traversal (starting from vertex 2): ");
graph.BFS(2);
}
}
#3 Breadth first search implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Structure to represent a queue
struct Queue {
int items[MAX_SIZE];
int front;
int rear;
};
// Function to initialize a queue
struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = -1;
queue->rear = -1;
return queue;
}
// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
return queue->front == -1;
}
// Function to add an element to the queue
void enqueue(struct Queue* queue, int value) {
if (queue->rear == MAX_SIZE - 1) {
printf("Queue is full\n");
} else {
if (queue->front == -1) {
queue->front = 0;
}
queue->rear++;
queue->items[queue->rear] = value;
}
}
// Function to remove an element from the queue
int dequeue(struct Queue* queue) {
int item;
if (isEmpty(queue)) {
printf("Queue is empty\n");
return -1;
} else {
item = queue->items[queue->front];
queue->front++;
if (queue->front > queue->rear) {
queue->front = queue->rear = -1;
}
return item;
}
}
// Function to perform Breadth-First Search
void BFS(int graph[][MAX_SIZE], int vertices, int start) {
struct Queue* queue = createQueue();
int visited[MAX_SIZE] = {0}; // Array to keep track of visited vertices
printf("Breadth-First Search starting from vertex %d:\n", start);
visited[start] = 1; // Mark the start vertex as visited
enqueue(queue, start);
while (!isEmpty(queue)) {
int currentVertex = dequeue(queue);
printf("%d ", currentVertex);
for (int i = 0; i < vertices; i++) {
if (graph[currentVertex][i] == 1 && !visited[i]) {
visited[i] = 1;
enqueue(queue, i);
}
}
}
printf("\n");
}
int main() {
int vertices, start;
printf("Enter the number of vertices: ");
scanf("%d", &vertices);
int graph[MAX_SIZE][MAX_SIZE];
printf("Enter the adjacency matrix:\n");
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
scanf("%d", &graph[i][j]);
}
}
printf("Enter the starting vertex: ");
scanf("%d", &start);
BFS(graph, vertices, start);
return 0;
}
#4 Breadth first search implement in C++
Code -
C++ Programming
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Graph {
public:
Graph(int vertices);
void addEdge(int v, int w);
void BFS(int startVertex);
private:
int vertices;
vector < vector<int>> adjList;
};
Graph::Graph(int vertices) : vertices(vertices) {
adjList.resize(vertices);
}
void Graph::addEdge(int v, int w) {
adjList[v].push_back(w);
}
void Graph::BFS(int startVertex) {
vector < bool> visited(vertices, false);
queue<int> q;
visited[startVertex] = true;
q.push(startVertex);
while (!q.empty()) {
int currentVertex = q.front();
cout << currentVertex << " ";
q.pop();
for (int adjacentVertex : adjList[currentVertex]) {
if (!visited[adjacentVertex]) {
visited[adjacentVertex] = true;
q.push(adjacentVertex);
}
}
}
}
int main() {
Graph g(6); // Create a graph with 6 vertices
// Add edges to the graph
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
cout << "Breadth-First Search starting from vertex 0:" << endl;
g.BFS(0);
return 0;
}
Demonstration
Breadth first search Data Structure and Algorithm