C++ program on Depth First Search on Graph

C++ program for Adjacency Matrix Representation of Graph and Depth First Search

 #include <iostream>

using namespace std;

void DFS(int);

int G[10][10],visited[10],n;    //n is no of vertices and graph is sorted in array G[10][10]

int main()

{

    int i,j;

    cout<<"Enter number of vertices:";

      cin>>n;

    //read the adjacency matrix

      cout<<"\nEnter adjacency matrix of the graph:";

      for(i=0;i<n;i++)

       for(j=0;j<n;j++)

                  cin>>G[i][j];

      //display the adjacency matrix

      cout<<"\n **Adjacency matrix**\n";

            for(i=0;i<n;i++)

             {

                  for(j=0;j<n;j++)

                        cout<<G[i][j];

                  cout<<"\n";

             }

    //visited is initialized to zero

   for(i=0;i<n;i++)

        visited[i]=0;

    cout<<"\n DFS of the graph:";

    DFS(0);

    return 0;

}

void DFS(int i)

{

    int j;

      cout<<i;

    visited[i]=1;

      for(j=0;j<n;j++)

       if(!visited[j]&&G[i][j]==1)

            DFS(j);

}

Output:

Enter number of vertices:3

Enter adjacency matrix of the graph:0

1

0

0

0

1

1

1

0

 **Adjacency matrix**

010

001

110

 DFS of the graph:012