Implementation of BFS for Graph using Adjacency List:
C++
#include
#include
#include
using namespace std;
// Function to perform Breadth First Search on a graph
// represented using adjacency list
void bfs(vector >& adjList, int startNode,
vector& visited)
{
// Create a queue for BFS
queue q;
// Mark the current node as visited and enqueue it
visited[startNode] = true;
q.push(startNode);
// Iterate over the queue
while (!q.empty()) {
// Dequeue a vertex from queue and print it
int currentNode = q.front();
q.pop();
cout << currentNode << " ";
// Get all adjacent vertices of the dequeued vertex
// currentNode If an adjacent has not been visited,
// then mark it visited and enqueue it
for (int neighbor : adjList[currentNode]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
// Function to add an edge to the graph
void addEdge(vector >& adjList, int u, int v)
{
adjList[u].push_back(v);
}
int main()
{
// Number of vertices in the graph
int vertices = 5;
// Adjacency list representation of the graph
vector > adjList(vertices);
// Add edges to the graph
addEdge(adjList, 0, 1);
addEdge(adjList, 0, 2);
addEdge(adjList, 1, 3);
addEdge(adjList, 1, 4);
addEdge(adjList, 2, 4);
// Mark all the vertices as not visited
vector visited(vertices, false);
// Perform BFS traversal starting from vertex 0
cout << "Breadth First Traversal starting from vertex "
"0: ";
bfs(adjList, 0, visited);
return 0;
}
C
#include
#include
#define MAX_VERTICES 100
// Structure to represent a node in adjacency list
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data)
{
struct Node* newNode
= (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to add an edge to the graph
void addEdge(struct Node* adjList[], int u, int v)
{
struct Node* newNode = createNode(v);
newNode->next = adjList[u];
adjList[u] = newNode;
}
// Function to perform Breadth First Search on a graph
// represented using adjacency list
void bfs(struct Node* adjList[], int vertices,
int startNode, int visited[])
{
// Create a queue for BFS
int queue[MAX_VERTICES];
int front = 0, rear = 0;
// Mark the current node as visited and enqueue it
visited[startNode] = 1;
queue[rear++] = startNode;
// Iterate over the queue
while (front != rear) {
// Dequeue a vertex from queue and print it
int currentNode = queue[front++];
printf("%d ", currentNode);
// Get all adjacent vertices of the dequeued vertex
// currentNode If an adjacent has not been visited,
// then mark it visited and enqueue it
struct Node* temp = adjList[currentNode];
while (temp != NULL) {
int neighbor = temp->data;
if (!visited[neighbor]) {
visited[neighbor] = 1;
queue[rear++] = neighbor;
}
temp = temp->next;
}
}
}
int main()
{
// Number of vertices in the graph
int vertices = 5;
// Adjacency list representation of the graph
struct Node* adjList[vertices];
for (int i = 0; i < vertices; ++i)
adjList[i] = NULL;
// Add edges to the graph
addEdge(adjList, 0, 1);
addEdge(adjList, 0, 2);
addEdge(adjList, 1, 3);
addEdge(adjList, 1, 4);
addEdge(adjList, 2, 4);
// Mark all the vertices as not visited
int visited[vertices];
for (int i = 0; i < vertices; ++i)
visited[i] = 0;
// Perform BFS traversal starting from vertex 0
printf(
"Breadth First Traversal starting from vertex 0: ");
bfs(adjList, vertices, 0, visited);
return 0;
}
Java
import java.util.LinkedList;
import java.util.Queue;
// Class to represent a graph using adjacency list
class Graph {
int vertices;
LinkedList[] adjList;
@SuppressWarnings("unchecked") Graph(int vertices)
{
this.vertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i < vertices; ++i)
adjList[i] = new LinkedList<>();
}
// Function to add an edge to the graph
void addEdge(int u, int v) { adjList[u].add(v); }
// Function to perform Breadth First Search on a graph
// represented using adjacency list
void bfs(int startNode)
{
// Create a queue for BFS
Queue queue = new LinkedList<>();
boolean[] visited = new boolean[vertices];
// Mark the current node as visited and enqueue it
visited[startNode] = true;
queue.add(startNode);
// Iterate over the queue
while (!queue.isEmpty()) {
// Dequeue a vertex from queue and print it
int currentNode = queue.poll();
System.out.print(currentNode + " ");
// Get all adjacent vertices of the dequeued
// vertex currentNode If an adjacent has not
// been visited, then mark it visited and
// enqueue it
for (int neighbor : adjList[currentNode]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
}
public class Main {
public static void main(String[] args)
{
// Number of vertices in the graph
int vertices = 5;
// Create a graph
Graph graph = new Graph(vertices);
// Add edges to the graph
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
// Perform BFS traversal starting from vertex 0
System.out.print(
"Breadth First Traversal starting from vertex 0: ");
graph.bfs(0);
}
}
Python3
from collections import deque
# Function to perform Breadth First Search on a graph
# represented using adjacency list
def bfs(adjList, startNode, visited):
# Create a queue for BFS
q = deque()
# Mark the current node as visited and enqueue it
visited[startNode] = True
q.append(startNode)
# Iterate over the queue
while q:
# Dequeue a vertex from queue and print it
currentNode = q.popleft()
print(currentNode, end=" ")
# Get all adjacent vertices of the dequeued vertex
# If an adjacent has not been visited, then mark it visited and enqueue it
for neighbor in adjList[currentNode]:
if not visited[neighbor]:
visited[neighbor] = True
q.append(neighbor)
# Function to add an edge to the graph
def addEdge(adjList, u, v):
adjList[u].append(v)
def main():
# Number of vertices in the graph
vertices = 5
# Adjacency list representation of the graph
adjList = [[] for _ in range(vertices)]
# Add edges to the graph
addEdge(adjList, 0, 1)
addEdge(adjList, 0, 2)
addEdge(adjList, 1, 3)
addEdge(adjList, 1, 4)
addEdge(adjList, 2, 4)
# Mark all the vertices as not visited
visited = [False] * vertices
# Perform BFS traversal starting from vertex 0
print("Breadth First Traversal starting from vertex 0:", end=" ")
bfs(adjList, 0, visited)
if __name__ == "__main__":
main()
C#
using System;
using System.Collections.Generic;
// Class to represent a graph using adjacency list
class Graph {
int vertices;
List[] adjList;
public Graph(int vertices)
{
this.vertices = vertices;
adjList = new List[ vertices ];
for (int i = 0; i < vertices; ++i)
adjList[i] = new List();
}
// Function to add an edge to the graph
public void AddEdge(int u, int v) { adjList[u].Add(v); }
// Function to perform Breadth First Search on a graph
// represented using adjacency list
public void BFS(int startNode)
{
// Create a queue for BFS
Queue queue = new Queue();
bool[] visited = new bool[vertices];
// Mark the current node as visited and enqueue it
visited[startNode] = true;
queue.Enqueue(startNode);
// Iterate over the queue
while (queue.Count != 0) {
// Dequeue a vertex from queue and print it
int currentNode = queue.Dequeue();
Console.Write(currentNode + " ");
// Get all adjacent vertices of the dequeued
// vertex currentNode If an adjacent has not
// been visited, then mark it visited and
// enqueue it
foreach(int neighbor in adjList[currentNode])
{
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.Enqueue(neighbor);
}
}
}
}
}
class MainClass {
public static void Main(string[] args)
{
// Number of vertices in the graph
int vertices = 5;
// Create a graph
Graph graph = new Graph(vertices);
// Add edges to the graph
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 3);
graph.AddEdge(1, 4);
graph.AddEdge(2, 4);
// Perform BFS traversal starting from vertex 0
Console.Write(
"Breadth First Traversal starting from vertex 0: ");
graph.BFS(0);
}
}
Javascript
// Class to represent a graph using adjacency list
class Graph {
constructor() {
this.adjList = {};
}
// Function to add an edge to the graph
addEdge(u, v) {
if (!this.adjList[u]) this.adjList[u] = [];
this.adjList[u].push(v);
}
// Function to perform Breadth First Search on a graph represented using adjacency list
bfs(startNode) {
// Create a queue for BFS
const queue = [];
const visited = new Array(Object.keys(this.adjList).length).fill(false);
// Mark the current node as visited and enqueue it
visited[startNode] = true;
queue.push(startNode);
// Iterate over the queue
while (queue.length !== 0) {
// Dequeue a vertex from queue and print it
const currentNode = queue.shift();
console.log(currentNode + " ");
// Get all adjacent vertices of the dequeued vertex currentNode
// If an adjacent has not been visited, then mark it visited and enqueue it
for (const neighbor of this.adjList[currentNode] || []) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}
}
}
// Create a graph
const graph = new Graph();
// Add edges to the graph
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
// Perform BFS traversal starting from vertex 0
console.log("Breadth First Traversal starting from vertex 0: ");
graph.bfs(0);...
Contact Us