Showing posts with label Adjacent nodes. Show all posts
Showing posts with label Adjacent nodes. Show all posts

Monday, 3 November 2014

Construct Graph and adding nodes and edges and displaying adjacency list using C++

#include<iostream>
#include<stdlib.h>
using namespace std;
void make_node(int n);
void add_edges();
void display();
int n;
struct edge;
struct node
{
    int data;
    struct node *below;
    struct edge *adj;
}*start,*temp,*last,*ptrx;

struct edge
{
    struct node *parent;
    struct edge *link;
}*first,*stop,*ptr;

int main()
{
    cout<<"\nEnter the number of nodes:";
    cin>>n;
    make_node(n);
    add_edges();
    display();
    return 0;
}

void make_node(int n)
{
    for(int i=0;i<n;i++)
    {
        if(start==nullptr)
        {
            start=new node;
            cout<<"\nEnter data in node "<<i+1<<" : ";
            cin>>start->data;
            start->below=nullptr;
            start->adj=nullptr;
            last=start;
        }
        else
        {
            temp=new node;
            cout<<"\nEnter data in node "<<i+1<<" : ";
            cin>>temp->data;
            last->below=temp;
            last=temp;
            last->below=nullptr;
            last->adj=nullptr;
            temp=nullptr;
        }
    }
}

void add_edges()
{
    int x,t;
    last=start;
    for(int i=0;i<n;i++,last=last->below)
    {
        cout<<"\nEnter number of edges in node "<<i+1<<" : ";
        cin>>x;
        ptrx=last;
        first=nullptr;
        for(int j=0;j<x;j++)
    {
        temp=start;
        if(first==nullptr)
        {
            first=new edge;
            cout<<"\nEnter the adjacent node "<<j+1<<" : ";
            cin>>t;
            for(int k=1;k<t;k++)
            temp=temp->below;
            first->parent=temp;
            first->link=nullptr;
            ptrx->adj=first;
            stop=first;
        }
        else
        {
            first=new edge;
            cout<<"\nEnter the adjacent node "<<j+1<<" : ";
            cin>>t;
            for(int k=1;k<t;k++)
            temp=temp->below;
            first->parent=temp;
            first->link=nullptr;
            stop->link=first;
            stop=first;
        }
    }
    }
}

void display()
{
    system("cls");
    cout<<"\nNode\t\t\tAdjacent node list";
    temp=start;
    for(int i=0;i<n;i++,temp=temp->below)
    {
        cout<<"\n"<<temp->data<<"\t\t\t\t";
        ptr=temp->adj;
        if(ptr!=nullptr)
        {
        while(ptr->link!=nullptr)
        {
            ptrx=ptr->parent;
            cout<<ptrx->data<<";";
            ptr=ptr->link;
        }
            ptrx=ptr->parent;
            cout<<ptrx->data;
        }
    }
}

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);

}