C++ program to implement Depth First Search algorithm

C++ program traverse the graph using Depth First Search algorithm. In second program I have created adjacency list from adjacency matrix and traverse it using DFS traversal.

C++ program to implement Depth First Search algorithm

#include<iostream>
using namespace std;
class graph
{
    int a[10][10],n,start;
public:
    void getdata();
    void dfs_traverse();
};
void graph::getdata()
{
    cout<<"Enter the number of vertices in the graph ";
    cin>>n;
    cout<<"Enter the adjacency matrix of graph "<<endl;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    cout<<"Enter the vertex from which you want to traverse ";
    cin>>start;
}
void graph::dfs_traverse()
{
    int *visited= new int[n];
    int stack[10],top=-1,i;
    for(int j=0;j<n;j++)
        visited[j]=0;
    cout<<"The Depth First Search Traversal : "<<endl;
    i=stack[++top]=start;
    visited[start]=1;
    while(top>=0)
    {
        i=stack[top];
        cout<<stack[top--]<<endl;
        for(int j=n-1;j>=0;j--)
            if(a[i][j]!=0&&visited[j]!=1)
            {
              stack[++top]=j;
              visited[j]=1;
            }
    }
}
int main()
{
    graph dfs;
    dfs.getdata();
    dfs.dfs_traverse();
    return 0;
}

C++ program to create adjacency list and implement Depth First Search algorithm

#include<iostream>
using namespace std;
struct graphnode
{
    int ver_no;
    graphnode *next;
};
class graph
{
    int a[10][10],n,start;
    graphnode *ver[10];
public:
    graph()
    {
        for(int i=0;i<10;i++)
            ver[i]=NULL;
    }
    void getdata();
    void dfs_traverse();
    void matrix_to_list();
};
void graph::getdata()
{
    cout<<"Enter the number of vertices ";
    cin>>n;
    cout<<"Enter the adjacency matrix\n";
    for(int i=0;i<n;i++)
        for(int y=0;y<n;y++)
            cin>>a[i][y];
    cout<<"Enter the starting node ";
    cin>>start;
}
void graph::matrix_to_list()
{
    graphnode *ne,*temp;
    for(int i=0;i<n;i++)
    {
        for(int y=n-1;y>=0;y--)
        {
            if(a[i][y]!=0)
            {
                ne=new graphnode;
                ne->ver_no=y;
                ne->next=NULL;
                if(ver[i]==NULL)
                {
                    ver[i]=ne;
                    temp=ne;
                }
                else
                {
                    temp->next=ne;
                    temp=temp->next;
                }
            }
        }
    }
}
void graph::dfs_traverse()
{
    int *visited= new int[n];
    graphnode *temp;
    int stack[10],top=-1,i;
    for(int j=0;j<n;j++)
        visited[j]=0;
    cout<<"Depth First Traversal "<<endl;
    stack[++top]=start;
    visited[start]=1;
    while(top>=0)
    {
        temp=ver[stack[top]];
        cout<<stack[top--]<<endl;
        while(temp!=NULL)
        {
            if(visited[temp->ver_no]!=1)
            {
              stack[++top]=temp->ver_no;
              visited[temp->ver_no]=1;
            }
            temp=temp->next;
        }
    }
}
int main()
{
    graph dfs;
    dfs.getdata();
    dfs.matrix_to_list();
    dfs.dfs_traverse();
    return 0;
}