Develop 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/BFS method
#include <stdio.h> #include <stdio.h>
const int MAX = 100;
const int SIZE = 10; void fnBreadthFirstSearchReach(int vertex, int g[MAX][MAX], int v[MAX], int n);
typedef struct { int iaItems[10]; int iFront; int iRear; }QUEUE;
void fnQInsert(QUEUE *stQueue, int elem);
int fnQDelete(QUEUE *stQueue); int fnQFull(QUEUE *stQueue); int fnQEmpty(QUEUE *stQueue);
int main(void) { int graph[MAX][MAX]; int visited[MAX]; int numVert, startVert, i,j;
printf("Enter the number of vertices : ");
scanf("%d", &numVert); printf("Enter the adjacency matrix :\n"); for (i=0; i<numVert; i++) visited[i] = 0; for (i=0; i<numVert; i++) for (j=0; j<numVert; j++) scanf("%d", &graph[i][j]); printf("Enter the starting vertex : "); scanf("%d", &startVert); fnBreadthFirstSearchReach(startVert- 1,graph,visited,numVert); printf("Vertices which can be reached from vertex %d are :- \n",startVert); for (i=0; i<numVert; i++) if (visited[i]) printf("%d ",i+1); printf("\n"); return 0; }
void fnBreadthFirstSearchReach(int vertex, int g[MAX][MAX], int
v[MAX], int n) { QUEUE stQueue; stQueue.iFront = 0; stQueue.iRear = -1; int frontVertex, i; v[vertex] = 1; fnQInsert(&stQueue, vertex); while (!fnQEmpty(&stQueue)) { frontVertex = fnQDelete(&stQueue); for (i=0; i<n; i++) { if (g[frontVertex][i] && !v[i]) { v[i] = 1; fnQInsert(&stQueue, i); } } } }
#include <stdio.h> const int MAX = 100; void fnDepthFirstSearch(int currentVertex, int v[MAX], int g[MAX][MAX], int n);
int main(void) { int i,j,k; int visited[MAX]; int graph[MAX][MAX]; int numVert, Vert; printf("Enter the number of vertices : "); scanf("%d", &numVert); for (i=0; i<numVert; i++) visited[i] = 0; printf("Enter the adjacency matrix :\n"); for (i=0; i<numVert; i++) for (j=0; j<numVert; j++) scanf("%d", &graph[i][j]); printf("Enter the source vertex : "); scanf("%d", &Vert); fnDepthFirstSearch(Vert,visited,graph,numVert); for (k=0; k<numVert; k++) { if(visited[k]) { printf("\nVertex %d is reachable\n", k+1); } else { printf("\nVertex %d is not reachable\n", k+1); } } return 0; }
void fnDepthFirstSearch(int currentVertex, int v[MAX], int
g[MAX][MAX], int n) { int i; v[currentVertex] = 1; for (i=0; i<n; i++) { if (g[currentVertex][i] && !v[i]) fnDepthFirstSearch(i,v,g,n); } }
Enter the number of vertices : 4
Enter the adjacency matrix : 0100 1000 0001 0010 Enter the source vertex : 3
