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:
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:
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 :
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:
