Key for important topicsDFS (depth first search) program in c++

/*  C++ Program to implement DFS Algorithm for Connected Graph */

#include<iostream>
using namespace std;

#define MAX 100

#define initial 1
#define visited 2

int n;    /* Number of nodes in the graph */
int adj[MAX][MAX]; /*Adjacency Matrix*/
int state[MAX]; /*Can be initial or visited */

void DF_Traversal();
void DFS(int v);
void create_graph();

int stack[MAX];
int top = -1;
void push(int v);
int pop();
int isEmpty_stack();

int main()
{
        create_graph();
        DF_Traversal();
}/*End of main()*/

void DF_Traversal()
{
        int v;

        for(v=0; v<n; v++)
                state[v]=initial;

        cout<<("\nEnter starting node for Depth First Search : ");
        cin>>(v);
        DFS(v);
        cout<< ("\n");
}/*End of DF_Traversal( )*/

void DFS(int v)
{
        int i;
        push(v);
        while(!isEmpty_stack())
        {
                v = pop();
                if(state[v]==initial)
                {
                        cout<<(v);
                        state[v]=visited;
                }
                for(i=n-1; i>=0; i--)
                {
                        if(adj[v][i]==1 && state[i]==initial)
                                push(i);
                }
        }
}/*End of DFS( )*/

void push(int v)
{
        if(top == (MAX-1))
        {
                cout<<("\nStack Overflow\n");
                return;
        }
        top=top+1;
        stack[top] = v;

}/*End of push()*/

int pop()
{
        int v;
        if(top == -1)
        {
                cout<<("\nStack Underflow\n");
                exit(1);
        }
        else
        {
                v = stack[top];
                top=top-1;
                return v;
        }
}/*End of pop()*/

int isEmpty_stack( )
{
  if(top == -1)
          return 1;
  else
          return 0;
}/*End if isEmpty_stack()*/

void create_graph()
{
        int i,max_edges,origin,destin;

        cout<<("\nEnter number of nodes : ");
        cin>>(n);
        max_edges=n*(n-1);

        for(i=1;i<=max_edges;i++)
        {
                cout<<"\nEnter edge( -1 -1 to quit )"<<i<<":";
                cin>>origin;
                cin>>destin;

                if( (origin == -1) && (destin == -1) )
                        break;

                if( origin >= n || destin >= n || origin<0 || destin<0)
                {
                        cout<<("\nInvalid edge!\n");
                        i--;
                }
                else
                {
                        adj[origin][destin] = 1;
                }
        }
}

Comments

Popular Posts