Scribd
Upload
3 views3 pages

Ds Program11

The document provides a C program for creating a graph of cities using an adjacency matrix and performing depth-first search (DFS) and breadth-first search (BFS) to find all reachable nodes from a given starting node. It includes functions for BFS and DFS traversal, user input for the number of vertices and the adjacency matrix, and options to choose the traversal method. The program also handles unreachable nodes by indicating them after the traversal.

Uploaded by

harry789
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 views3 pages

Ds Program11

The document provides a C program for creating a graph of cities using an adjacency matrix and performing depth-first search (DFS) and breadth-first search (BFS) to find all reachable nodes from a given starting node. It includes functions for BFS and DFS traversal, user input for the number of vertices and the adjacency matrix, and options to choose the traversal method. The program also handles unreachable nodes by indicating them after the traversal.

Uploaded by

harry789
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

Design, Develop and Implement a Program in C for the following operations on Graph(G)of Cities:

a) Create a Graph of N cities using Adjacency Matrix.


b) Print all the nodes reachable from a given starting node in a digraph using DFS/BFSmethod.

#include<stdio.h>

#include<stdlib.h>

int a[50][50], n, visited[50];

int q[20], front = -1, rear = -1;

int s[20], top = -1, count = 0;

void bfs(int v)

int i, cur;

visited[v] = 1;

q[++rear] = v;

while (front != rear)

cur = q[++front];

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

if ((a[cur][i] == 1) && (visited[i] == 0))

q[++rear] = i;

visited[i] = 1;

printf("%d ", i);

}
void dfs(int v)

int i;

visited[v] = 1;

s[++top] = v;

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

if (a[v][i] == 1 && visited[i] == 0)

printf("%d ", i);

dfs(i);

int main()

int ch, start, i, j;

printf("\nEnter the number of vertices in graph:");

scanf("%d", & n);

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

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

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

scanf("%d", & a[i][j]);

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

visited[i] = 0;
printf("\nEnter the starting vertex: ");

scanf("%d", & start);

printf("\n==>1. BFS: Print all nodes reachable from a given starting node");

printf("\n==>2. DFS: Print all nodes reachable from a given starting node");

printf("\n==>3:Exit");

printf("\nEnter your choice: ");

scanf("%d", & ch);

switch (ch)

case 1:

printf("\nNodes reachable from starting vertex %d are: ", start);

bfs(start);

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

if (visited[i] == 0)

printf("\nThe vertex that is not reachable is %d", i);

break;

case 2:

printf("\nNodes reachable from starting vertex %d are:\n", start);

dfs(start);

break;

case 3:

exit(0);

default:

printf("\nPlease enter valid choice:");

You might also like