Brittle Things: Depth first search cpp program

CPP Program to implement DFS

#include<iostream.h>

#include<conio.h>

#include<stdlib.h>

#define MAX_NODE 50

class graph

{ private:

struct node

{ int vertex;

node *next;

};

node *adj[MAX_NODE];

int totNodes;

int stack[MAX_NODE],top;

int queue[MAX_NODE],f,r;

public:

graph();

void push(int);

int pop(void);

int is_stk_empty(void);

void q_insert(int);

int q_delete(void);

int is_q_empty(void);

void inserttograph(int,int);

void deletefromgraph(int);

void DispAdjList(void);

void DFS_traversal(int);

void BFS_traversal(int);

void insertedge(int,int);

void deleteedge(int,int);

void search(int);

};

graph::graph()

{ for(int i=0;i<MAX_NODE;i++)

adj[i]=NULL;

top=-1;

f=r=-1;

}

void graph::push(int item)

{ top=top+1;

stack[top]=item;

}

int graph::pop()

{ int deldata=stack[top];

top=top-1;

return(deldata);

}

int graph::is_stk_empty()

{ if(top==-1)

return(1);

else

return(0);

}

void graph::q_insert(int item)

{ if(r==MAX_NODE-1)

r=0;

else

r++;

queue[r]=item;

if(f==-1) f=0;

}

int graph::q_delete()

{ int delitem=queue[f];

if(f==r)

f=r=-1;

else

if(f==MAX_NODE-1)

f=0;

else

f++;

return(delitem);

}

int graph::is_q_empty(void)

{ if(f==-1)

return(1);

else

return(0);

}

void graph::inserttograph(int index,int neigbour)

{ node *newnode, *old, *current,*head;

newnode=new node;

newnode->vertex=neigbour;

newnode->next=NULL;

if(adj[index]==NULL)

{ head=new node;

head->vertex=index;

head->next=newnode;

adj[index]=head;

return;

}

for(current=adj[index]->next;current!=NULL; current=current->next)

old=current;

old->next=newnode;

}

void graph::deletefromgraph(int index)

{ node *old, *current, *temp;

if(adj[index]->vertex!=index)

{ cout<<"No such node exists";

return;

}

current=adj[index]->next;

while(current!=NULL)

{ temp=current;

current=current->next;

delete temp;

}

adj[index]=NULL;

for(int i=0;i<MAX_NODE;i++)

{ if(adj[i]!=NULL)

{ old=adj[i];

for(current=adj[i]->next;current!=NULL;current=current->next)

{ if(current->vertex==index)

{ old->next=current->next;

break;

}

old=current;

}

delete current;

}

cout<<"The node"<<index<<"and all of its edges removed";

return;

}

void graph::DispAdjList(void)

{ node *current;

for(int i=0;i<MAX_NODE;i++)

if(adj[i]!=NULL)

{ cout<<"Node="<<adj[i]->vertex<<"Neighbours=";

for(current=adj[i]->next;current!=NULL;current=current->next)

cout<<current->vertex<<" ";

cout<<endl;

}

void graph::DFS_traversal(int start_node)

{ node *tmp;

int N,v,status[MAX_NODE];

const int ready=1,wait=2,processed=3;

for(int i=0;i<MAX_NODE;i++)

if(adj[i]!=NULL) status[i]=ready;

push(start_node);

while(is_stk_empty()!=1)

{ N = pop();

cout<<" "<<N;

status[N]=processed;

tmp = adj[N]->next;

while(tmp!=NULL)

{ v = tmp->vertex;

if(status[v]==ready)

{ push(v);

status[v]=wait;

}

tmp=tmp->next;

}

void graph::BFS_traversal(int start_node)

{ node *tmp;

int N,v,status[MAX_NODE];

const int ready=1,wait=2,processed=2;

for(int i=0;i<MAX_NODE;i++)

if(adj[i]!=NULL) status[i]=ready;

q_insert(start_node);

while(is_q_empty()!=1)

{ N=q_delete();

status[N]=processed;

cout<<" "<<N;

tmp=adj[N]->next;

while(tmp!=NULL)

{ v=tmp->vertex;

if(status[v]==ready)

{ q_insert(v);

status[v]=wait;

}

tmp=tmp->next;

}

void graph::insertedge(int nod1, int nod2)

{ if((adj[nod1]==NULL)||(adj[nod2]==NULL))

{ cout<<"Either or both of the nodes does not exist in the graph";

return;

}

node *newnode1, *newnode2;

newnode1=new node;

newnode1->next=adj[nod1]->next;

newnode1->vertex=nod2;

adj[nod1]->next = newnode1;

newnode2 = new node;

newnode2->next=adj[nod2]->next;

newnode2->vertex=nod1;

adj[nod2]->next =newnode2;

}

void graph::deleteedge(int nod1, int nod2)

{ node *current, *old;

int flag=1;

old=adj[nod1];

for(current=adj[nod1]->next;current!=NULL;current=current->next)

{ if(current->vertex==nod2)

{ old->next=current->next;

delete current;

break;

}

old=current;

}

if(current==NULL) flag=0;

old=adj[nod2];

for(current=adj[nod2]->next;current!=NULL;current=current->next);

{ if(current->vertex==nod1)

{ old->next=current->next;

delete current;

// break;

}

old=current;

}

if(current==NULL) flag=0;

if(flag)

cout<<"Edge deleted!";

else

cout<<"This edge dose not exist in graph";

}

void graph::search(int index)

{ node *current;

int flag=0;

for(int i=0;i<MAX_NODE;i++)

if(adj[i]->vertex==index)

{ cout<<"Node "<<adj[i]->vertex<<"Exist.Its neighbours are";

for(current=adj[i]->next;

current!=NULL;

current=current->next)

cout<<current->vertex<<" ";

flag=1;

}

if(!flag)

cout<<"Node "<<index<<" does not exist in the graph";

}

void main()

{ int c, nod1, nod2;

char cont;

graph g;

while(1)

{ clrscr();

cout<<"Perform the Following Operations on a Graph Data Structure";

cout<<"___________________________"<<endl;

cout<<"\n 1.Input nodes to Graph";

cout<<"\n 2.display Adjancency Lists of the graph";

cout<<"\n 3.Depth First Traversal";

cout<<"\n 4.Breadth First Traversel";

cout<<"\n 5.Insert an Edge";

cout<<"\n 6.Delete An Edge";

cout<<"\n 7.Delete a Node";

cout<<"\n 8.Search for a Node";

cout<<"\n 9.Exit from Program";

{ cout<<"Select your choice(1:9):";

cin>>c;

cout<<" ";

}

while((c<1)||(c>9));

if(c==9) exit(1);

clrscr();

switch(c)

{ case 1 :

clrscr();

int element, neighbours, neighbour_value;

{ clrscr();

cout<<"\nEnter the node to insert (0 to 49):";

cin>>element;

cout<<"\nEnter no. of nodes in the adjecency list of node"<<element<<endl;

cout<<"--> That is Total neighbours of"<<element<<" : ";

cin>>neighbours;

for(int j=1;j<=neighbours;j++)

{ cout<<"Enter neighbour# "<<j<<" : ";

cin>>neighbour_value;

g.inserttograph(element,neighbour_value);

}

cout<<endl<<"Add More Nodes (Y/N):";

cin>>cont;

}

while((cont=='y')||(cont=='Y'));

break;

case 2 :

clrscr();

cout<<"The result of DFS traversal is"<<endl;

g.DispAdjList();

break;

case 3 :

int sn;

clrscr();

cout<<"Enter the Start Node:";

cin>>sn;

cout<<"The result of DFS traversal is"<<endl;

g.DFS_traversal(sn);

break;

case 4 :

int stnode;

clrscr();

cout<<"Enter the Start Node: ";

cin>>stnode;

cout<<"The result of BFS traversal is"<<endl;

g. BFS_traversal(stnode);

break;

case 5:

{ clrscr();

cout<<"We assume that an undirected edge is to be inserted"<<endl;

cout<<"Enter the index of the first node: ";

cin>>nod1;

cout<<"Enter the index of the second node: ";

cin>>nod2;

g.insertedge(nod1,nod2);

cout<<endl<<"Add More Edges (Y/N)";

cin>>cont;

}

while((cont=='y')||(cont=='Y'));

break;

case 6 :

{ clrscr();

cout<<"We assume that an undirected edge is to be deleted"<<endl;

cout<<"Enter the index of the first node: ";

cin>>nod1;

cout<<"Enter the index of the second node: ";

cin>>nod2;

g.deleteedge(nod1,nod2);

cout<<endl<<"Delete More Edges (Y/N):";

cin>>cont;

}

while((cont=='y')||(cont=='Y'));

break;

case 7:

{ clrscr();

cout<<"We assume that a node from an undirected graph is to be deleted ";

cout<<"Enter the index of the node to delete: ";

cin>>nod1;

g.deletefromgraph(nod1);

cout<<endl<<"Delete More Nodes (Y/N):";

cin>>cont;

}

while((cont=='y')||(cont=='Y'));

break;

case 8 :

clrscr();

{ clrscr();

cout<<"The node to search:";

cin>> nod1;

g.search(nod1);

cout<<endl<<"Delete More Nodes (Y/N):";

cin>>cont;

}

while((cont=='y')||(cont=='Y'));

break;

}

cout<<endl<<"Press Any Key to Continue...";

getch();

}

Brittle Things

Pages

Friday, 7 December 2012

Depth first search cpp program

No comments:

Post a Comment