Scribd
Upload
3 views2 pages

BFS Java

This Java program implements a Breadth-First Search (BFS) algorithm on an undirected graph using an adjacency matrix. It allows users to input the number of vertices and edges, add edges between vertices, and specify a starting vertex for the BFS traversal. The program uses a queue to manage the traversal order and prints the vertices in the order they are visited.

Uploaded by

amanmohammad9410
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views2 pages

BFS Java

This Java program implements a Breadth-First Search (BFS) algorithm on an undirected graph using an adjacency matrix. It allows users to input the number of vertices and edges, add edges between vertices, and specify a starting vertex for the BFS traversal. The program uses a queue to manage the traversal order and prints the vertices in the order they are visited.

Uploaded by

amanmohammad9410
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

import [Link].

Scanner;

class BFSGraph {

static final int MAX = 10; // Maximum number of vertices


static int[][] adjMatrix = new int[MAX][MAX];
static int[] visited = new int[MAX];

// Queue implementation using array


static int[] queue = new int[MAX];
static int front = -1, rear = -1;

static int vertices;

// Enqueue operation
static void enqueue(int value) {
if (rear == MAX - 1)
return; // Queue overflow
if (front == -1)
front = 0;
queue[++rear] = value;
}

// Dequeue operation
static int dequeue() {
if (front == -1 || front > rear)
return -1; // Queue underflow
return queue[front++];
}

// BFS Traversal
static void BFS(int startVertex) {

// Initialize visited array


for (int i = 0; i < vertices; i++) {
visited[i] = 0;
}

[Link]("Breadth First Search starting from vertex " + startVertex + ":");

enqueue(startVertex);
visited[startVertex] = 1;

while (front <= rear) {


int currentVertex = dequeue();
[Link](currentVertex + " ");

for (int i = 0; i < vertices; i++) {


if (adjMatrix[currentVertex][i] == 1 && visited[i] == 0) {
enqueue(i);
visited[i] = 1;
}
}
}
[Link]();
}

// Initialize graph
static void initializeGraph() {
for (int i = 0; i < MAX; i++) {
visited[i] = 0;
for (int j = 0; j < MAX; j++) {
adjMatrix[i][j] = 0;
}
}
}

// Add edge (Undirected graph)


static void addEdge(int src, int dest) {
adjMatrix[src][dest] = 1;
adjMatrix[dest][src] = 1;
}

// Main method
public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("Enter number of vertices: ");


vertices = [Link]();

[Link]("Enter number of edges: ");


int edges = [Link]();

initializeGraph();

[Link]("Enter edges (source destination):");


for (int i = 0; i < edges; i++) {
int src = [Link]();
int dest = [Link]();
addEdge(src, dest);
}

[Link]("Enter starting vertex for BFS: ");


int startVertex = [Link]();

BFS(startVertex);

[Link]();
}
}

You might also like