Heapsort

#include<stdio.h>
#include<conio.h>
#define max 50

struct elem
{
 int info;
}ar[max],tr[max],item;

int noe,i,ptr,par,ind,left,right;

void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of elements : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max);
 printf("\n\n Enter the '%d' elements of array in unsorted order : ",noe);
 for(i=1;i<=noe;i++)
  scanf("%d",&ar[i].info);
 printf("\n\n The '%d' elements of array in unsorted order :",noe);
 for(i=1;i<=noe;i++)
  printf(" %d",ar[i].info);
}

void ins_heap(int n)
{
 tr[n] = ar[n];
 if(n != 1)
 {
 ptr = n;
 par = ptr/2;
 while(ptr>1 && tr[par].info < tr[ptr].info)
 {
  item = tr[par];
  tr[par] = tr[ptr];
  tr[ptr] = item;
  ptr = par;
  par = ptr/2;
 }
 }
}

void del_heap(int n)
{
 item = tr[1];
 tr[1] = tr[n];
 tr[n] = item;
 par = 1; left = 2; right = 3;
 ind = 0;
 while(par < n && ind == 0)
 {
  if(tr[left].info > tr[par].info && tr[left].info > tr[right].info && left<n)
  {
  item = tr[left];
  tr[left] = tr[par];
  tr[par] = item;
  par = left;
  }
  else if(tr[right].info > tr[par].info && tr[left].info < tr[right].info  && right<n)
  {
  item = tr[right];
  tr[right] = tr[par];
  tr[par] = item;
  par = right;
  }
  else
   ind = 1;
  left = 2*par;
  right = 2*par+1;
 }
 ar[n] = tr[n];
}

void hp_srt()
{
 for(i=1;i<=noe;i++)
  ins_heap(i);
 i = noe;
 while(i>=1)
 {
 del_heap(i);
 i--;
 }
 printf("\n\n The '%d' elements of array in sorted order :",noe);
 for(i=1;i<=noe;i++)
  printf(" %d",ar[i].info);
}

void main()
{
clrscr();
inp_dat();
hp_srt();
getch();
}

Depth-First Search (DFS) Algorithm

#include<stdio.h>

#include<conio.h>
#include<iostream.h>
#include"graph01.cpp"          /* Refer this Source Code */
#define max 50

struct stack
{
 int top;
 struct node *ver[max];
}stk;

void DFS()
{
 printf("\n Enter the starting Node : ");
 cin>>item;
 stk.top = 1;
 find_node();
 if(loc != NULL)
 {
  loc->status = 2;
  stk.ver[stk.top] = loc;
 }
 else
  printf("\n\n Node not found !!\n\n");
 printf("\n\n The DFS Traversal Is : ");
 while(stk.top != 0)
 {
  loc = stk.ver[stk.top--];
  printf(" %c",loc->info);
  loc->status = 3;
  //qu.front++;
  ptre = loc->adj;
  while(ptre!=NULL)
  {
   if(ptre->dest->status == 1)
   {
    ptre->dest->status = 2;
    stk.ver[++stk.top] = ptre->dest;
   }
  ptre = ptre->link;
  }
 }
}

void main()
{
clrscr();
create_node();
create_vertices();
DFS();
getch();
}

Breadth-First Search (BFS) Algorithm

#include<stdio.h>

#include<conio.h>
#include<iostream.h>
#include"graph01.cpp"          /* Refer this Source Code */
#define max 50

struct queue
{
 int front;
 int rear;
 struct node *ver[max];
}qu;

char string[max];

void BFS()
{
 printf("\n Enter the starting Node : ");
 cin>>item;
 qu.front = qu.rear = 1;
 find_node();
 if(loc != NULL)
 {
  loc->status = 2;
  qu.ver[qu.front] = loc;
 }
 else
  printf("\n\n Node not found !!\n\n");
 printf("\n\n The BFS Traversal Is : ");
 while(qu.front != 0)
 {
  loc = qu.ver[qu.front];
  printf(" %c",loc->info);
  loc->status = 3;
  qu.front++;
  ptre = loc->adj;
  while(ptre!=NULL)
  {
   if(ptre->dest->status == 1)
   {
    ptre->dest->status = 2;
    qu.rear += 1;
    qu.ver[qu.rear] = ptre->dest;
   }
  ptre = ptre->link;
  }
  if(qu.front > qu.rear)
   qu.front = 0;
 }
}

void main()
{
clrscr();
create_node();
create_vertices();
BFS();
getch();
}

Breadth and Depth First Search (BFS and DFS) Algorithms (Complex)

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct node
{
char info;
int status;
struct node *next;
struct adjlist *adj;
}*start,*temp,*temp1,*q,*svar;



char queue[100];
int front=-1;
int rear=-1;

struct adjlist
{
char dest;
int status;
struct adjlist *link;
}*edge1,*p,*r;

struct node *findnode(struct node *,char);
void input(char);
void inputedge(char,char);


void dfsinitial(struct node *);
void dfssearch(struct node *);
void bfsinitial(struct node *);
void bfssearch(struct node *);
void queueinsert(char);
char queuedelete();
void backs();


void main()
{

int ch,choice=1;
char n,n1,n2;
clrscr();
do
{
printf("1. Input \n");
printf("2. input edge\n");
printf("3. bfs  search\n");





printf("Enter your choice\n");
scanf("%d",&ch);
fflush(stdin);

switch(ch)
{
case 1: printf("Enter the node\n");
scanf("%c",&n);
input(n);
 break;

case 2: printf("Enter the nodes between whom you want an edge\n");
scanf("%c\t%c",&n1,&n2);
inputedge(n1,n2);
break;




case 3: printf("The bfs search is as follows\n");
 bfsinitial(start);
 backs();
 break;
default: printf("Wrong choice\n");
}
printf("\nDo you want to enter more??\n");
scanf("%d",&choice);
}while(choice==1);
getch();

}


void backs()
{
printf("\b");
}

void input(char item)      //TO ADD NODES
{
struct node *ptr;
ptr=(struct node *)malloc(sizeof(struct node));

if(ptr==NULL)
{
printf("Memory full\n");
}

if(start==NULL)
{
ptr->info=item;
ptr->next=NULL;
ptr->adj=NULL;
start=ptr;
}

else
{
ptr->info=item;
ptr->next=start;
ptr->adj=NULL;
start=ptr;
}
ptr->status=1;

}

void inputedge(char item1,char item2)                 // TO ADD AN EDGE
{
temp=findnode(start,item1);
temp1=findnode(start,item2);
if(temp==NULL || temp1==NULL)
{
printf("Node not present\n");
}
edge1=(struct adjlist *)malloc(sizeof(struct adjlist));
edge1->dest=temp1->info;
if(temp->adj==NULL)
{


edge1->link=NULL;
temp->adj=edge1;
}
else
{
edge1->link=temp->adj;
temp->adj=edge1;
}
edge1->status=1;
}

struct node *findnode(struct node *graph,char item)  // TO FIND A NODE
{
while(graph!=NULL && graph->info!=item)
{
graph=graph->next;
}
if(item==graph->info)
{
return graph;
}
return 0;
}








void bfsinitial(struct node *start)
{

char a;
q=start;
queueinsert(q->info);
q->status=2;
a=queuedelete();
printf("%c",a);


bfssearch(q);
}

void bfssearch(struct node *yum)
{
char b,d;
r=yum->adj;
if(r->status==1)
{

while(r!=NULL && (r->status==1))
{

d=r->dest;
queueinsert(d);
r->status=2;
r=r->link;

}


b=queuedelete();
printf("%c",b);

svar=findnode(start,b);

bfssearch(svar);
}

}

void queueinsert(char s)
{
 if(front==-1 && rear==-1)
 {
 front=0;
 rear=0;
  queue[rear]=s;
 }
 else
 {
 rear++;
 queue[rear]=s;
 }

 }

 char queuedelete()
 {
 char rtn;
 rtn=queue[front];
 if(front==-1 && rear==-1)
 {
 printf("The queue is empty\n");
 }
 else if(front==rear)
 {
 front=-1;
 rear=-1;
 }

 else
 {
front++;
 }
 return rtn;
 }

Breadth and Depth First Search (BFS and DFS) Algorithms (Simple)

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include"graph01.cpp"      /* Refer this Source Code */
#define max 50

struct queue
{
 int front;
 int rear;
 struct node *ver[max];
}qu;

struct stack
{
 int top;
 struct node *ver[max];
}stk;


void BFS()
{
 qu.front = qu.rear = 1;
 if(loc != NULL)
 {
  loc->status = 2;
  qu.ver[qu.front] = loc;
 }
 else
  printf("\n\n Node not found !!\n\n");
 printf("\n\n The BFS Traversal Is : ");
 while(qu.front != 0)
 {
  loc = qu.ver[qu.front];
  printf(" %c",loc->info);
  loc->status = 3;
  qu.front++;
  ptre = loc->adj;
  while(ptre!=NULL)
  {
   if(ptre->dest->status == 1)
   {
    ptre->dest->status = 2;
    qu.rear += 1;
    qu.ver[qu.rear] = ptre->dest;
   }
  ptre = ptre->link;
  }
  if(qu.front > qu.rear)
   qu.front = 0;
 }
}

void DFS()
{
 stk.top = 1;
 if(loc != NULL)
 {
  loc->status = 2;
  stk.ver[stk.top] = loc;
 }
 else
  printf("\n\n Node not found !!\n\n");
 printf("\n\n The DFS Traversal Is : ");
 while(stk.top != 0)
 {
  loc = stk.ver[stk.top--];
  printf(" %c",loc->info);
  loc->status = 3;
  ptre = loc->adj;
  while(ptre!=NULL)
  {
   if(ptre->dest->status == 1)
   {
    ptre->dest->status = 2;
    stk.ver[++stk.top] = ptre->dest;
   }
  ptre = ptre->link;
  }
 }
}

void main()
{
clrscr();
create_node();
create_vertices();
printf("\n\n Enter the starting node : ");
cin>>item;
find_node();
int_stats();
BFS();
find_node();
int_stats();
DFS();
getch();
}