Write a C program to implement an algorithm based on Depth-First Search to test

Question

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)

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.