Scribd
Upload
3 views3 pages

BFS Code

This document contains a C program that implements the Breadth-First Search (BFS) algorithm for traversing a graph. It allows the user to input the number of vertices and edges, as well as the edges themselves, and then performs BFS starting from a specified vertex. The program outputs the traversal order along with the distance and previous vertex for each vertex in the graph.

Uploaded by

2024-1-50-010
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

BFS Code

This document contains a C program that implements the Breadth-First Search (BFS) algorithm for traversing a graph. It allows the user to input the number of vertices and edges, as well as the edges themselves, and then performs BFS starting from a specified vertex. The program outputs the traversal order along with the distance and previous vertex for each vertex in the graph.

Uploaded by

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

#include<stdio.

h>
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

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

void enqueue(int v)
{
if (rear == MAX - 1)
return;

if (front == -1)
front = 0;

queue[++rear] = v;
}

int dequeue()
{
if (front == -1 || front > rear)
return -1;

return queue[front++];
}

void BFS(int adj[MAX][MAX], int n, int s)


{
int color[MAX], d[MAX], prev[MAX];

for (int u = 0; u < n; u++)


{
if (u != s)
{
color[u] = WHITE;
d[u] = 9999;
prev[u] = -1;
}
}

color[s] = GRAY;
d[s] = 0;
prev[s] = -1;

front = rear = -1;


enqueue(s);

printf("BFS traversal: ");

while (front != -1 && front <= rear)


{
int u = dequeue();
if (u == -1) break;

printf("%d ", u);

for (int v = 0; v < n; v++)


{
if (adj[u][v] == 1 && color[v] == WHITE)
{
color[v] = GRAY;
d[v] = d[u] + 1;
prev[v] = u;
enqueue(v);
}
}

color[u] = BLACK;
}

printf("\n");

printf("\nVertex\tDist\tPrev\n");
for (int i = 0; i < n; i++)
{
printf("%d\t%d\t%d\n", i, d[i], prev[i]);
}
}

int main()
{
int n, e;
int adj[MAX][MAX] = {0};

printf("Enter number of vertices: ");


scanf("%d", &n);

printf("Enter number of edges: ");


scanf("%d", &e);

printf("Enter edges (u v):\n");


for (int i = 0; i < e; i++)
{
int u, v;
scanf("%d %d", &u, &v);
adj[u][v] = 1;
adj[v][u] = 1;
}

int start;
printf("Enter starting vertex: ");
scanf("%d", &start);

BFS(adj, n, start);

return 0;
}

You might also like