Lab program 7b: Check whether a given graph is connected or not using DFS method.

Description:

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root(selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Algorithm

      DFS(G,v)   ( v is the vertex where the search starts )

         Stack S := {};   ( start with an empty stack )

         for each vertex u, set visited[u] := false;

         push S, v;

         while (S is not empty) do

            u := pop S;

            if (not visited[u]) then

               visited[u] := true;

               for each unvisited neighbour w of u

                  push S, w;

            end if

         end while

      END DFS()

 Solution:

#include<stdio.h>

int visit[20],n,adj[20][20],s,count=0;

void dfs(int v)

{

  int w;

  visit[v]=1;

  count++;

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

    if((adj[v][w]==1) && (visit[w]==0))

      dfs(w);

}

void main()

{

  int v,w;

  printf("Enter the no.of vertices:");

  scanf("%d",&n);

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

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

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

      scanf("%d",&adj[v][w]);

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

      visit[v]=0;

    dfs(1);

  if(count==n)

   printf("\nThe graph is connected");

  else

   printf("The graph is not connected");

}

OUTPUT 1 :

Enter the no.of vertices:4

Enter the adjacency matrix:

1 1 0 0

1 1 1 1

0 1 1 1

0 1 1 1

The graph is connected

OUTPUT 2:

Enter the no.of vertices:4

Enter the adjacency matrix:

1 1 1 0

1 1 0 0

1 0 1 0

0 0 0 0

The graph is not connected