Krushkals Minimum cost spanning tree

Aim:  To implement krushkals algorithm to generate minimum spanning tree

Program:

#include<stdio.h>

int cost[10][10],i,j,k,n,a,b,ne,min=999,set[10],mincost=0,u,v;

void main()

{

clrscr();

printf("minimum cost spanning tree with krushkals");

printf("\nenter no of vertices");

scanf("%d",&n);

printf("\nenter cost matrix");

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

scanf("%d",&cost[i][j]);

if(cost[i][j]==0)

cost[i][j]=999;

}

}

for(i=1;i<n;i++)

set[i]=i;

ne=0;

while(ne<n-1)

{

min=999;

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

if(cost[i][j]<min)

{

min=cost[i][j];

a=i;

b=j;

}

}

}

u=find(a);

v=find(b);

if(u!=v)

{

unin(u,v);

ne++;

printf("%d edges(%d,%d) is cost is %d\n",ne,a,b,min);

mincost=mincost+min;

}

cost[a][b]=cost[b][a]=999;

}

printf("\n total min cost spanning tree is %d",mincost);

getch();

}

int find(int x)

{

return set[x];

}

int unin(int i,int j)

{

int k;

for(k=1;k<=n;k++)

{

if(set[k]==j)

set[k]=i;

}

}

Input:

   the input is given in adjacent matrix  from for below graph

Output:

 

Depth First Search(DFS)

Aim: To implement Depth First Search non recursively

Program:

#include<stdio.h>

#include<conio.h>

int n,am[10][10],stk[10],st,v,i,j,visited[10],top=0;

void main()

{

clrscr();

printf("enter number of vertices");

scanf("%d",&n);

printf("enter adjacent matrix");

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

scanf("%d",&am[i][j]);

visited[i]=0;

}

printf("enter source node:");

scanf("%d",&st);

dfs(st);

getch();

}

dfs(int st)

{

top++;

stk[top]=st;

while(top>0)

{

v=stk[top];

top--;

if(visited[v]==0)

{

visited[v]=1;

printf("-->%d",v);

}

for(i=n;i>=1;i--)

{

if(am[v][i]==1 && visited[i]==0)

{

if(instack(i)==0)

{

top++;

stk[top]=i;

}

}

}

}

}

int instack(int n)

{

for(j=1;j<=top;j++)

{rix

if(stk[j]==n)

return 1;

}

return 0;

}

Input:

   The input is given in adjacency matrix as given below graph

Output:

Breadth First Search (BFS)

Aim: Implement Breadth first Search(BFS) non recursively itself

Program:

#include<stdio.h>

int visited[10],st,q[10],v,i,j,am[10][10],n,front=0,rear=0;

void main()

{

clrscr();

printf("enter number of vertices");

scanf("%d",&n);

printf("enter adjacent matrix");

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

scanf("%d",&am[i][j]);

visited[i]=0;

}

printf("enter source node");

scanf("%d",&st);

bfs(st);

getch();

}

int bfs(int st)

{

q[rear]=st;

rear++;

while(front<rear)

{

v=q[front];

front++;

if(visited[v]==0)

{

visited[v]=1;

printf("-->%d",v);

}

for(i=1;i<=n;i++)

{

if(am[v][i]==1 && visited[i]==0)

{

if(inqueue(i)==0)

{

q[rear]=i;

rear++;

}

}

}

}

}

int inqueue(int n)

{

int j;

for(j=front;j<rear;j++)

{

if(q[j]==n)

return  1;

}

return 0;

}

input:

  input is given in the adjacent matrix for the below graph

output :

Heap sort program in c program - heap sort in data structures

Aim: To sort elements by heap order( max heap) in C program

program:

#include<stdio.h>

void main()

{

int n,a[50],i;

clrscr();

printf("enter elements to be entered");

scanf("%d",&n); printf("enter elements");

for(i=1;i<=n;i++)

scanf("%d",&a[i]);

heapsort(a,n);

printf("after sorting the elements are");

for(i=1;i<=n;i++)

printf("%d ",a[i]);

getch();

}

int  heapsort(int a[],int n)

{

int t,i; heapify(a,n);

for(i=n;i>=2;i--)

{

t=a[i];  

       a[i]=a[1];

a[1]=t;

adjust(a,1,i-1); 

} 

return;

}

int  heapify(int a[],int n)

{

int i; for(i=n/2;i>=1;i--) 

adjust(a,i,n);

return;

}

int adjust(int a[],int i,int n)

{ 

     int j,item,t; 

      j=2*i; item=a[i];

while(j<=n)

{

if(j<n && a[j]<a[j+1]) 

j=j+1;

if(item<=a[j]) 

{

t=a[j/2];  

a[j/2]=a[j];

a[j]=t;

} 

j=2*j;

}

}

Output:

Queue using linked list cprogram

Aim:Implementation of queue using linked list in C program

to download file   :click here

Program:

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

void enque(int);

void deque();

void display();

struct queue

{

int data;

struct queue *next;

};

typedef struct queue node;

node *rear,*front,*new,*dfront;

void main()

{

int ch,item;

clrscr();

front=rear=NULL;

while(1)

{

printf("1.enque\t2.deque\t3.display\t4.exit\n");

printf("enter your choice");

scanf("%d",&ch);

switch(ch)

{

case 1:

printf("enter the element to insert");

scanf("%d",&item);

enque(item);

break;

case 2:

deque();

break;

case 3:

printf("elements in queue are: ");

display();

break;

default :

exit(0);

}

}

}

void enque(int item)

{

if(rear==NULL)

{

rear=(node *)malloc(sizeof(node));

rear->data=item;

rear->next=NULL;

front=rear;

}

else

{

new=(node *)malloc(sizeof(node));

new->data=item;

new->next=NULL;

rear->next=new;

rear=new;

}

}

void deque()

{

if(front==NULL)

printf("underflow\n");

else

{

printf("element deleted is %d\n",front->data);

if(front==rear)

front=rear=NULL;

else

front=front->next;

}

}

void display()

{       dfront=front;

while(dfront!=NULL)/*dfront means duplicate front*/

{

printf("%d ",dfront->data);

dfront=dfront->next;

}

printf("\n");

}

Output:

Binary search tree operations(insertion,deletion) cprogram

Aim: to implement binary search operation(insertion,deletion) in c program
program:

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

void insertion(int);

void display();

struct bsearch

{

int data;

struct bsearch *rchild,*lchild;

};

typedef struct  bsearch node;

node *root,*ptr,*new,*parent,*temro;

void main()

{

int ch,item,rt,item2;

clrscr();

root=(node *)malloc(sizeof(node));

printf("enter the root for bst tree");

scanf("%d",&rt);

root->data=rt;

root->rchild=NULL;

root->lchild=NULL;

while(1)

{

printf("1.insert  2.delete  3.display  4.eixt");

printf("\tenter your choice");

scanf("%d",&ch);

switch(ch)

{

case 1:

printf("enter the item to insert");

scanf("%d",&item);

insertion(item);

break;

case 2:

printf("enter the item to be deleted");

scanf("%d",&item);

deletion(root,item);

break;

case 3:

printf("inoder=");

display(root);

printf("\n");

break;

default :

exit(0);

}

}

}

void insertion(int item)

{

ptr=root;

while(ptr!=NULL)

{

if(ptr->data==item)

{

printf("item already exit insertion not possible");

exit(0);

}

else if(item<ptr->data)

{

parent=ptr;

ptr=ptr->lchild;

}

else

{

parent=ptr;

ptr=ptr->rchild;

}

if(ptr==NULL)

{

new=(node *)malloc(sizeof(node));

new->data=item;

new->lchild=NULL;

new->rchild=NULL;

if(item<parent->data)

parent->lchild=new;

else

parent->rchild=new;

}

}

}

void display(struct bsearch *root)

{

if(root!=NULL)

{

display(root->lchild);

printf("%d ",root->data);

display(root->rchild);

}

}

deletion(struct bsearch *root,int item)

{

node *ptr1,*insuc;

int found=0,cas,temp;

ptr=root;

while(ptr!=NULL)

{

if(ptr->data==item)

{

found=1;

break;

}

else if(item<ptr->data)

{

parent=ptr;

ptr=ptr->lchild;

}

else

{

parent=ptr;

ptr=ptr->rchild;

}

}

if(found==0)

printf("item to be deleted is not found");

else

{

if(ptr->lchild==NULL&&ptr->rchild==NULL)

cas=1;

else if(ptr->lchild!=NULL&&ptr->rchild!=NULL)

cas=3;

else

cas=2;

}

if(cas==1)

{

if(parent->lchild->data==item)

{

parent->lchild=NULL;

free(ptr);

}

else

{

parent->rchild=NULL;

free(ptr);

}

}

if(cas==2)

{

if(parent->lchild->data==item)

{

if(ptr->lchild!=NULL)

{

parent->lchild=ptr->lchild;

free(ptr);

}

else

{

parent->lchild=ptr->rchild;

free(ptr);

}

}

else

{

if(ptr->lchild!=NULL)

{

parent->rchild=ptr->lchild;

free(ptr);

}

else

{

parent->rchild=ptr->rchild;

free(ptr);

}

}

}

if(cas==3)

{

ptr1=ptr->rchild;

while(ptr1!=NULL)

{

insuc=ptr1;

ptr1=ptr1->lchild;

}

temp=insuc->data;

ptr->data=temp;

deletion(insuc,temp);

}

}

output:

Representation of polynomials using linked list

Aim: To Represent polynomials using linked list in cprogram

program:

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

void display();

void insert();

struct poly

{

int coef,exp; 

struct poly *next;

};

typedef struct poly node;

node *header,*ptr,*temp;

void main()

{

int ch;

clrscr(); 

        header->coef=NULL;

header->exp=NULL;

header->next=NULL;

while(1)

{ 

printf("1.insert poly\t 2.display\t 3.exit\n"); 

printf("enter your choice");  

                scanf("%d",&ch);

switch(ch)

{  

case 1: insert();  

                                        break;  

case 2:  

display(); 

break;  

default:  

exit(0); 

} 

}

}

void insert()

{ 

       int coef,exp; 

       printf("enter coefficients,exponen for term ");

scanf("%d%d",&coef,&exp);

ptr=(node *)malloc(sizeof(node));

ptr->coef=coef; ptr->exp=exp; 

       ptr->next=NULL; 

       if(header->next==NULL) '

header->next=ptr;

else

{  

               temp=header;  

               while(temp->next!=NULL) 

temp=temp->next; 

temp->next=ptr;

}

}

void display()

{

printf("header->"); 

      ptr=header->next;

while(ptr!=NULL)

{ 

printf("[%d][%d]->",ptr->coef,ptr->exp); 

ptr=ptr->next; 

       }

printf("NULL\n");
}

out put:

Operations On linked lists(Insertion,Deletion,Reverse list) Cprogram

Aim: To implement linked list operations(Insertion,Deletion,Reverse list) in Cprogram

Program:

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

void create();

void deletion();

void display();

void insert();

void reverse();

struct list

{

int data;

struct list *next;

};

typedef struct list node;

node *header;

void main()

{

int ch,item;

clrscr();

while(1)

{

printf("1.create  2.insert  3.deletion  4.display  5.reverese  6.exit\n");

printf("enter your choice");

scanf("%d",&ch);

switch(ch)

{

case 1:

create();

break;

case 3:

deletion();

break;

case 4:

display();

break;

case 2:

insert();

break;

case 5:

reverse();

break;

default :

exit(0);

}

}

}

void create()

{

header=(node*)malloc(sizeof(node));

header->data=NULL;

header->next=NULL;

}

void insert()

{

node *new,*ptr,*prev;

int item,pos,element;

printf("enter the item you want 2 insert");

scanf("%d",&item);

new=(node*)malloc(sizeof(node));

new->data=item;

printf("enter position of insertio 1.begining\t 2.end\t 3.any position");

scanf("%d",&pos);

switch(pos)

{

case 1:

new->next=header->next;

header->next=new;

break;

case 2:

ptr=header;

while(ptr->next!=NULL)

ptr=ptr->next;

new->next=NULL;

ptr->next=new;

break;

case 3:

printf("enter the element after which you want 2 insert:");

scanf("%d",&element);

ptr=header->next;

while(ptr->next!=NULL&&ptr->data!=element);

ptr=ptr->next;

if(ptr->data==element)

{

new->next=ptr->next;

ptr->next=new;

}

else

{

printf("element not found\n");

break;

}

}

}

void deletion()

{

node *ptr,*prev;

int pos,item;

printf("1.delete front \t2. delete last\t 3.delete any");

scanf("%d",&pos);

switch(pos)

{

case 1:

{

ptr=header->next;

if(ptr==NULL)

printf("list is empty\n");

else

{

header->next=ptr->next;

free(ptr);

}

break;

}

case 2:

{

ptr=header->next;

prev=header;

if(ptr==NULL)

printf("list is empty\n");

else

{

while(ptr->next!=NULL)

{

prev=ptr;

ptr=ptr->next;

}

prev->next=NULL;

free(ptr);

}

break;

}

case 3:

{

ptr=header->next;

prev=header;

printf("enter the item you want to delete");

scanf("%d",&item);

while(ptr->data!=item&&ptr->next!=NULL)

{

prev=ptr;

ptr=ptr->next;

}

if(ptr->data==item)

{

prev->next=ptr->next;

free(ptr);

}

else

printf("item not found\n");

break;

}

}

}

void display()

{

node *ptr;

ptr=header->next;

printf("header->");

while(ptr!=NULL)

{

printf("%d->",ptr->data);

ptr=ptr->next;

}

printf("NULL\n");

}

void reverse()

{

node *p1,*p2,*p3,*last;

p1=header->next;

if(p1==NULL)

printf("list is empty");

else

{

p2=p1->next;

p3=p2->next;

last=header->next;

while(last->next!=NULL)

last=last->next;

if(p3==NULL)

{

p1->next=NULL;

p2->next=p1;

header->next=p2;

}

else

{

p1->next=NULL;

while(p3!=last)

{

p2->next=p1;

p1=p2;

p2=p3;

p3=p3->next;

}

p2->next=p1;

p3->next=p2;

header->next=p3;

}

}

display();

}

output: