Write a C program to implement an algorithm based on DepthFi

Write a C program to implement an algorithm based on Depth-First Search to test the connectivity of a given network. Input: Adjacency matrix (refer to sample program on page 6 for reading in an adjacency matrix) Output: The sequence that vertices are being visited The vertices of each connected component of a given graph The parent of each vertex (a vertex p is the parent of vertex c if c is visited from p) Use your program to test the following network. A graph G(V, E) with the following adjacency matrix: (0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0)

Solution

i) First Question Answer:

#include<stdio.h>

#include<conio.h>

#define maxV 20

int a[maxV][maxV], visited[maxV], size;

void dfs(int vertex)

{

int i;

visited[vertex] = 1;

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

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

  {

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

   dfs(i);

  }

}

void main()

{

int i, j, count = 0;

clrscr();

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

scanf(\"%d\",&size);

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

{

  visited[i] = 0;

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

   a[i][j] = 0;

}

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

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

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

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

dfs(1);

printf(\"\ \");

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

{

  if(visited[i])

   count++;

}

if(count == size)

  printf(\"\ Graph is connected\");

else

  printf(\"\ Graph is not connected\");

getch();

}

ii) Second Question Answer:

I\'m test the given matrix, using above program.

Output is as follows:

1 --> 2

2 --> 3

3 --> 4

Graph is not connected