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

DESCRIPTION:

Depth-first search is a graph traversal algorithm, which has a very wide application area. This algorithm may be used for finding out number of components of a graph, topological order of its nodes or detection of cycles.Itis an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) 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()

CODE:

#include <iostream>
#include <cstdlib>
using namespace std;

const int MAX = 100;


void DepthFirstSearch(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])
            DepthFirstSearch(i,v,g,n);
}

int main()
{

    int i,j,k;
    int visited[MAX];
    int graph[MAX][MAX];
    int numVert;

    cout << "Enter the number of vertices : ";
    cin >> numVert;

    for (i=0; i<numVert; i++)
        visited[i] = 0;

    cout << "Enter the adjacency matrix :\n";

    for (i=0; i<numVert; i++)
        for (j=0; j<numVert; j++)
            cin >> graph[i][j];

    for (i=0; i<numVert; i++)
    {
        for (k=0; k<numVert; k++)
            visited[k] = 0;

        DepthFirstSearch(i,visited,graph,numVert);

        for (k=0; k<numVert; k++)
        {
            if (!visited[k])
            {
            cout << "\nGraph is not connected since there is no path between " << i << " and " << k << endl;

            exit(0);
            }
        }
    }

    cout << "\nGraph is connected."<< endl;
    return 0;
}

OUTPUTS

Enter the number of vertices : 4

Enter the adjacency matrix :

0 1 0 0

0 0 1 0

0 0 0 1

1 0 0 0

Graph is connected.