design analysis and algorithm

/ *5. BREADTH FIRST SEARCH */


#include
#include
int a[10][10],visited[10],n;
void search_from1(int);
void main()
{
int i,j;
clrscr();
cout<<"\n Enter the number of nodes:";
cin>>n;
cout<<"\n Enter the adjancency matrix:\n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
cout<<"\nEnter the value of "<cin>>a[i][j];
}
cout<<"\n Nodes are visited in the order";
for(i=1;i<=n;i++)
if(visited[i]==0)
search_from1(i);
getch();
}

void search_from1(int z)
{
int i,j;
cout<<"-->"<visited[z]=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(visited[i]==0)
if(a[z][j]!=0)
search_from1(i);
break;
}
getch();
}






OUTPUT:


BREADTH FIRST SEARCH



Enter the number of nodes:4
Enter the adjancency matrix:

Enter the value of 12 element 1
Enter the value of 13 element 0
Enter the value of 14 element 0
Enter the value of 21 element 1
Enter the value of 23 element 0
Enter the value of 24 element 1
Enter the value of 31 element 1
Enter the value of 32 element 0
Enter the value of 34 element 0
Enter the value of 41 element 0
Enter the value of 42 element 1
Enter the value of 43 element 1

Nodes are visited in the order
-->1-->2-->3-->4

*6. DEPTH FIRST SEARCH * /



#include
#include

int a[10][10],visited[10],n;
void search_from(int);
void main()
{
int i,j;
clrscr();
cout<<"\n Enter the number of nodes:";
cin>>n;
cout<<"\n Enter the adjancency matrix:\n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
cout<<"\nEnter the value of "<cin>>a[i][j];
}
cout<<"\n Nodes are visited in the order";
for(i=1;i<=n;i++)
if(visited[i]==0)
search_from(i);
getch();
}

void search_from(int k)
{
int i,j;
cout<<"-->"<visited[k]=1;
for(i=1;i<=n;i++)
if(visited[i]==0)
if(a[k][i]!=0)
search_from(i);
getch();
}
OUTPUT:


DEPTH FIRST SEARCH



Enter the number of nodes:5
Enter the adjancency matrix:

Enter the value of 12 element 0
Enter the value of 13 element 1
Enter the value of 14 element 0
Enter the value of 15 element 0
Enter the value of 21 element 0
Enter the value of 23 element 0
Enter the value of 24 element 0
Enter the value of 25 element 1
Enter the value of 31 element 0
Enter the value of 32 element 1
Enter the value of 34 element 1
Enter the value of 35 element 0
Enter the value of 41 element 0
Enter the value of 42 element 0
Enter the value of 43 element 0
Enter the value of 45 element 0
Enter the value of 51 element 0
Enter the value of 52 element 0
Enter the value of 53 element 0
Enter the value of 54 element 0

Nodes are visited in the order
-->1-->3-->2-->5-->4



/ *7. BINARY TREE TRAVERSAL */



#include
#include
#include

struct bnode
{
int data;
struct bnode *left,*right;
}*bt;

void create()
{
struct bnode *temp,*p,*pre;
int flag,key,d;
bt=NULL;
cout<<"\n \t Read the value until -1 to exit:\n\t ";
cin>>d;
while(d!=-1)
{
temp=(struct bnode *)(malloc(sizeof(struct bnode)));
temp->data=d;
temp->left=NULL;
temp->right=NULL;
if(bt==NULL)
bt=temp;

else
{
p=bt;
pre=bt;

while(p!=NULL)
{
key=p->data;


if(d{
flag=0;
pre=p;
p=p->left;
}




else if(d>key)
{
flag=1;
pre=p;
p=p->right;
}
}

if(flag==0)
pre->left=temp;
else
pre->right=temp;
}
cin>>d;
}
}


void preord(struct bnode *p)
{
if(p==NULL)
return;
cout<<"\t"<data;
if(p->left!=NULL)
preord(p->left);
if(p->right)
preord(p->right);
}


void postord(struct bnode *p)
{
if(p==NULL)
return;
if(p->left)
postord(p->left);
if(p->right)
postord(p->right);
cout<<"\t"<data;

}







void inord(struct bnode *p)
{
if(p==NULL)
return;

if(p->left)
inord(p->left);
cout<<"\t"<data;
if(p->right)
inord(p->right);
}

void main()
{
clrscr();
create();
cout<<"\n\tINORDER TRAVERSAL\n\t";
inord(bt);
cout<<"\n\tPREORDER TRAVERSAL\n\t";
preord(bt);
cout<<"\n\tPOSTORDER TRAVERSAL\n\t";
postord(bt);
getch();
}




















OUTPUT:


BINARY TREE TRAVERSAL
~~~~~~~~~~~~~~~~~~~~~~~~~~



Read the value until -1 to exit:
45 67 89 34 12 78 110 -1

INORDER TRAVERSAL
12 34 45 67 78 89 110

PREORDER TRAVERSAL
45 34 12 67 89 78 110

POSTORDER TRAVERSAL
12 34 78 110 89 67 45


/ *8. SHORTEST PATH * /

#include
#include

void shortestpath(int ,int);
int graph,costs=32760,cost1,num,sor,dest,edge;
int from[20],to[20],cost[20],path[10];
void shortestpath(int graph,int z)
{
int temp,k=0,i=-1,p[10];
for(temp=z;temp{
if(graph==from[temp])
{
p[k]=graph;
i++;
if(to[temp]==dest)
{
cost1=cost1+cost[temp];
if(cost1{
costs=cost1;
for(z=0;z<=i;z++)
path[z]=p[z];
num=temp;
break;
}
}
else
{
graph=to[temp];
cost1=cost1+cost[temp];
k++;
}
}
}
}
void main()
{
int i,z,cost2;
clrscr();
cout<<"\n Enter the number of edge:";
cin>>edge;
cout<<"\nEnter the source:";
cin>>sor;
cout<<"\nEnter the destination";
cin>>dest;
cout<<"\nDestination"<<"\t\t"<<"Cost";
for(i=0;i{
cout<<"From";
cin>>from[i];
cout<<"\nTo";
cin>>to[i];
cout<<"\nCost";
cin>>cost[i];
}
for(i=0;i{
if(sor==from[i])
{
graph=to[i];
cost2=cost[i];
for(z=i;z{
if(graph==from[z])
{
cost1=cost2;
shortestpath(graph,z);
}
else if(graph==dest)
{
cost1=cost2;
if(cost1{
costs=cost1;
num=0;
break;
}
}
}
}
}
cout<<"Cost:"<cout<<"Path:"<for(z=0;zcout<<"->"<cout<<"->"<getch();
}

OUTPUT:
SHORTEST PATH

Enter the number of edge: 3

Enter the source: 1
Enter the destination: 3
Source Destination Cost
From1

To2

Cost7
From1

To5

Cost7
From1

To3

Cost78
Cost: 78, Path: 1->3



/* 9.QUEENS PROBLEM USING BACKTRACKING */

#include
#include
#include
#include
#include

class queen
{
int n,x[100];
public:
queen();
void nqueen(int,int);
int place(int,int);
};

queen::queen()
{
int k=1;
textcolor(GREEN);
cprintf("Enter the number of queens:");
cin>>n;
nqueen( k, n);
}

void queen::nqueen(int k,int n)
{
for(int i=1;i<=n;i++)
{
if(place(k,i))
{
x[k]=i;
clrscr();
if(k==n)
{
for(int j=1;j<=n;j++)
{textcolor(x[j]);
gotoxy(1,j);
cprintf("queen %d : %d",j,x[j]);
}
getch();

break;
}
else
nqueen(k+1,n);
}
}
return;
}

int queen::place(int k,int i)
{
int j;
for(j=1;j<=k;j++)
{
if((x[j]==i)||(abs(x[j]-i)==abs(j-k)))
return 0;
}
return 1;
}

void main()
{
clrscr();
queen q;
}































OUTPUT:


/* QUEENS PROBLEM USING BACKTRACKING */


Enter the number of queens: 8
queen 1: 1
queen 2: 5
queen 3 : 8
queen 4 : 6
queen 5 : 3
queen 6 : 7
queen 7 : 2
queen 8 : 4


queen 1: 8
queen 2: 4
queen 3: 1
queen 4: 3
queen 5: 6
queen 6: 2
queen 7: 7
queen 8: 5


/*10. KNAPSACK USING BACKTRACKING */

#include
#include

class knapsack
{
int m,n,w[10],p[10],fw,fp,x[10],y[10],b,c;
float r[10];
int bound(int,int,int);

public:
knapsack();
void bknap(int,int,int);
void display();
};

knapsack::knapsack()
{
fp=-1;
cout<<"\n Enter the no of items:";
cin>>n;
cout<<"\n Enter the capacity of the bag:";
cin>>m;
for(int i=1;i<=n;i++)
{

a:cout<<"\n Enter the weight and profit for the item "<cin>>w[i]>>p[i];
r[i]=(float)p[i]/w[i];
if(i!=1)
if(r[i-1]{
cout<<"\n This entry is not valid \n";
goto a;
}
}
}

void knapsack::display()
{
cout<<"\n\n The selected items are \n\n";
for(int i=1;i<=n;i++)
cout<<" "<cout<for(int j=1;j<=n;j++)
cout<<" "<<"**";
cout<for(i=1;i<=n;i++)
cout<<" "<cout<<"\n\n Final weight="<cout<<"\n\n Final profit="<}

void knapsack::bknap(int k,int cp,int cw)
{
if(cw+w[k]<=m)
{
y[k]=1;
if(kif(((cp+p[k])>fp)&&(k==n))
{
fp=cp+p[k];
fw=cw+w[k];
for(int j=1;j<=k;j++)
x[j]=y[j];
}
}

if(bound(cp,cw,k)>=fp)
{
y[k]=0;
if(kif((cp>fp)&&(k==n))
{
fp=cp;
fw=cw;
for(int j=1;j<=k;j++)
x[j]=y[j];
}
}
}

int knapsack::bound(int cp,int cw,int k)
{
b=cp;
c=cw;
for(int i=k+1;i<=n;i++)
{
c=c+w[i];
if(cb=b+p[i];
else return(b+(1-(c-m)/w[i])*p[i]);
}
return b;
}

void main()
{
clrscr();
cout<<"\n\t\t\t KNAPSACK USING BACKTRACKING";
cout<<"\n\t\t\t ***************************";
knapsack ob;
int k=1,cp=0,cw=0;
ob.bknap(k,cp,cw);
ob.display();
getch();
}



OUTPUT:




KNAPSACK USING BACKTRACKING
**********************************
Enter the no of items: 8
Enter the capacity of the bag: 110
Enter the weight and profit for the item 1:1 11
Enter the weight and profit for the item 2:11 21
Enter the weight and profit for the item 3:21 31
Enter the weight and profit for the item 4:23 33
Enter the weight and profit for the item 5:33 43
Enter the weight and profit for the item 6:43 53
Enter the weight and profit for the item 7:45 55
Enter the weight and profit for the item 8:55 65


The selected items are

1 2 3 4 5 6 7 8
** ** ** ** ** ** ** **
1 1 1 0 1 1 0 0

Final weight=109

Final profit=159