Scribd
Upload
3 views4 pages

BFS and DFS Graph Traversal in C

The document contains a C program that implements Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms for traversing a graph represented by an adjacency matrix. It allows the user to input the number of vertices, the adjacency matrix, and choose between BFS and DFS to explore the graph. The program also checks if the graph is connected based on the DFS traversal results.

Uploaded by

shivanshucbhatt
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 views4 pages

BFS and DFS Graph Traversal in C

The document contains a C program that implements Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms for traversing a graph represented by an adjacency matrix. It allows the user to input the number of vertices, the adjacency matrix, and choose between BFS and DFS to explore the graph. The program also checks if the graph is connected based on the DFS traversal results.

Uploaded by

shivanshucbhatt
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

#include <stdio.

h>

#include <stdlib.h>

int a[20][20], q[20], visited[20], reach[20];

int n, i, j, f = 0, r = -1, count = 0;

/* BFS function */

void bfs(int v)

for (i = 1; i <= n; i++)

if (a[v][i] && !visited[i])

visited[i] = 1;

q[++r] = i;

if (f <= r)

bfs(q[f++]);

/* DFS function */

void dfs(int v)

reach[v] = 1;

for (i = 1; i <= n; i++)

{
if (a[v][i] && !reach[i])

printf("\n%d -> %d", v, i);

count++;

dfs(i);

int main()

int v, choice;

printf("Enter the number of vertices: ");

scanf("%d", &n);

/* Initialize arrays */

for (i = 1; i <= n; i++)

visited[i] = 0;

reach[i] = 0;

q[i] = 0;

printf("Enter the adjacency matrix:\n");

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

scanf("%d", &a[i][j]);
printf("\n1. BFS\n2. DFS\n3. Exit");

printf("\nEnter your choice: ");

scanf("%d", &choice);

switch (choice)

case 1:

printf("Enter the starting vertex: ");

scanf("%d", &v);

if (v < 1 || v > n)

printf("Invalid starting vertex");

break;

visited[v] = 1;

bfs(v);

printf("Nodes reachable from %d are:\n", v);

for (i = 1; i <= n; i++)

if (visited[i])

printf("%d ", i);

break;

case 2:

printf("Enter the starting vertex: ");


scanf("%d", &v);

dfs(v);

if (count == n - 1)

printf("\nGraph is connected");

else

printf("\nGraph is not connected");

break;

case 3:

exit(0);

default:

printf("Invalid choice");

return 0;

You might also like