Monday, 3 November 2014

Breadth First Search (BFS) and Depth First Search (DFS) C++ code

# define SIZE 10
#include<iostream>
#include<stdlib.h>
using namespace std;
void build(int n);
void process(int i);
char name[SIZE],que[SIZE];
int n,c,k,i,ptr=0,flag,h,select;
struct BFS
{
    char node;
    int frend[SIZE],index;

}ob[SIZE];


int main()
{
    cout<<"\nEnter the number of nodes:";
    cin>>n;
    build(n);
    que[0]=ob[0].node;
    k++;
    system("cls");
    cout<<"\n1:BFS\n2:DFS\nYour choice:";
    cin>>select;
    cout<<"Nodes          Queue Status";
    process(0);
    cout<<"\n\n\n";
}

void build(int n)
{
    int i,j,d;
    char temp;
    for(i=0;i<n;i++)
    {
        cout<<"\nEnter the name of node "<<i+1<<" : ";
        cin>>name[i];
        ob[i].node=name[i];
        ob[i].index=1;
    }

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

            cout<<"\nEnter number of adjacent nodes for node "<<name[i]<<" : ";
            cin>>c;
            for(d=0;d<c;d++)
            {
                cout<<"\nEnter adjacent node "<<d+1<<" : ";
                cin>>temp;
                for(int z=0;z<n;z++)
                {
                    if(ob[z].node==temp)
                    ob[i].frend[d]=z;
                }
            }

         ob[i].frend[d]=-1;
    }
}

void process(int i)
{

    if(ptr==k || k==-1)
    return;
    if(select==1)
    cout<<endl<<endl<<que[ptr];
    else
    cout<<endl<<endl<<ob[i].node;
    ob[i].index=3;
    c=0;
    while(ob[i].frend[c]!=-1)
    {
        flag=0;
        for(h=ptr;h<k;h++)
        {if(que[h]==ob[ob[i].frend[c]].node || ob[ob[i].frend[c]].index==3 )
        flag=1;}

        if(flag==0)
        {
        que[k++]=ob[ob[i].frend[c]].node;
        ob[ob[i].frend[c]].index=2;
        }
        c++;
    }
    cout<<"               ";
    if(select==1)
   {
    for(h=ptr+1;h<k;h++)
    {
        cout<<que[h]<<" , ";
    }
    for(i=0;i<n;i++)
    {
        if(que[ptr+1]==ob[i].node)
        break;
    }
    ptr++;
   }
   else
   {
        for(h=1;h<k;h++)
    {
        cout<<que[h]<<" , ";
    }
    for(i=0;i<n;i++)
    {
        if(que[k-1]==ob[i].node)
        break;
    }
    k--;
   }
    process(i);

}

No comments:

Post a Comment