PRIM'S ALGORITHM TO FIND MINIMUM SPANNING TREE

#include<stdio.h>
#define max 25
int g[max][max],v[max],n,sum;
void prims(int s);
int main(){
int s;
sum=0;
printf("enter number of vertices\n");
scanf("%d",&n);
printf("enter adjacent matrix\n");
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&g[i][j]);
}}
prims(0);
printf("min cost req is:%d\n",sum);
return 0;
}
void prims(int s){
int i,j,m=9999,k,m1,l;
v[s]=1;
m1++;
do{
for(i=0;i<n;i++){
m=9999;
if(v[i]==1){
for(j=0;j<n;j++){
if((g[i][j]!=0)&&(m>=g[i][j])&&v[j]!=1)
{
m=g[i][j];
k=i;
l=j;}
}
}}
printf("edge:%d--->%d\n",k,l);
printf("visited:%d",v[l]);
sum+=g[k][l];
v[l]=1; m1++;}while(m1!=n);
return;
}

SINGLE SOURCE SHORTEST PATH PROBLEM(DIJKSTRA'S ALGORITHM) 'C' PROGRAM

1. #include<stdio.h>
2. #include<limits.h>
3. int n;
4. int adj[10][10],vi[10];
5. int dist[10];
6. void shortest(int v);
7. int min();
8. int main(){
9. int i,j,s;
10. printf("enter number of vertices\n");
11. scanf("%d",&n);
12. for(i=1;i<=n;i++){
13. dist[i]=INT_MAX;
14. printf("%d\t",dist[i]);
15. }
16. printf("enter adjacency matrix\n");
17. for(i=1;i<=n;i++)
18. for(j=1;j<=n;j++)
19. scanf("%d",&adj[i][j]);
20. printf("enter source vertex to start\n");
21. scanf("%d",&s);
22. shortest(s);
23. printf("shortest distances from vertex %d are\n",s);
24. for(i=1;i<=n;i++){
25. if(dist[i]<INT_MAX&&vi[i]==1)
26. printf("cost:%d\tedge:(%d,%d)\n",dist[i],s,i);
27. }
28. return 0;
29. }
30.  void shortest(int v){
31. int i,j,u;
32. for(i=1;i<=n;i++){
33. vi[i]=-1;
34. if(adj[v][i]!=0)
35. dist[i]=adj[v][i];
36. }
37. vi[v]=1;
38. for(j=2;j<=n;j++){
39. u=min();
40. printf("%d\n",u);
41. vi[u]=1;
42. for(i=1;i<=n;i++){
43. if((adj[u][i]!=0)&&(dist[i]>(dist[u]+adj[u][i]))&&(vi[i]==-1)){
44. dist[i]=(dist[u]+adj[u][i]);
45. }
46. }
47. }
48. return;
49. }
50. int min(){
51.  int i,t=dist[1],j;
52. for(i=1;i<=n;i++){
53. if((dist[i]<t)&&(vi[i]==-1))
54. {
55. t=dist[i];
56. }}
57. for(j=1;j<=n;j++){
58. if(t==dist[j]&&vi[j]==-1)
59. break;}
60. return j;
61. }

QUICK SORT -'C' PROGRAM

#include<stdio.h>
#include<limits.h>
#define max 25
int arr[max];
int partition(int arr[],int l,int h);
void quick(int l,int h);
int main(){
int n;
printf("enter num: \n");
scanf("%d",&n);
printf("enter array elements\n");
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
arr[n]=INT_MAX;
quick(0,n);
printf("elements after sorting are\n");
for(int i=0;i<n;i++)
printf("%d\t",arr[i]);
}
int partition(int arr[],int l,int h)
{
int v=arr[l],i=l,j=h,temp;
do{
do{
i=i+1;
}while(arr[i]<v);
do{
j=j-1;
}while(arr[j]>v);
if (i<j)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}while(i<j);
arr[l]=arr[j];arr[j]=v;
return j;
}
void quick(int l,int h){
int j;
if(l<h)
{
j=partition(arr,l,h);
quick(l,j);
quick(j+1,h);
}
}

C PROGRAM FOR BINARY SEARCH USING RECURSION

#include<stdio.h>
void bin(int l,int h,int arr[],int s);
int main()
{
int s,i,k,arr[10]={0};
printf("enter array elements\n");
for(i=0;i<5;i++)
scanf("%d",&arr[i]);
printf("enter element to search\n");
scanf("%d",&s);
bin(0,4,arr,s);//CALL TO RECURSIVE FUN
return 0;
}
void bin(int l,int h,int arr[],int s){
int m;
if(l<=h){
m=(l+h)/2;
if(arr[m]==s){
printf("element found at %d",m+1);
}
else if(s<arr[m]){
 bin( l,m-1,arr,s);//RECURSIVE CALLS
}
else 
 bin( m+1,h,arr,s);}
else
printf("element not found\n");
return;
}

HEAP SORT USING C PROGRAM

# include<stdio.h>
#define Max 50
void heapup(int arr[],int,int);
void heap(int arr[],int n);
int main(){
int Heap[Max],n,i,j;
printf("enter number of elements in array\n");
scanf("%d",&n);
printf("enter  elements of array\n");
for(i=1;i<=n;i++)
{
scanf("%d",&Heap[i]);
heapup(Heap,i,n);
}

heap(Heap,n);
for(i=1;i<=n;i++){
printf("%d\t",Heap[i]);
}
return 0;
}
void heapup(int arr[],int i,int n){
int temp=arr[i],t,j=2*i;
while(j<=n){
if((j<n)&&(arr[j]<arr[j+1]))
j=j+1;
if(temp>arr[j])
break;
arr[j/2]=arr[j];
j=2*j;
}
arr[j/2]=temp;
}
void heap(int arr[],int n){
int t,k=n;
do{
t=arr[k];
arr[k]=arr[1];
arr[1]=t;
k--;
heapup(arr,1,k);
}while(k>0);
}

C PROGRAM TO PERFORM MERGE SORT

#include<stdio.h>
int a[100];
int t[100];
void merge(int low,int high);
void sort(int l,int h);
int main()
{
int i,n;
printf("enter size");
scanf("%d",&n);
printf("enter elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
merge(0,n-1);
printf("sorted array is ");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
return 0;
}
void merge(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge(low,mid);
merge(mid+1,high);
sort(low,high);
}
return;
}
void sort(int l,int h)
{

int mid=(l+h)/2;
int l1=l,l2=mid+1,i=l;
for(;l1<=mid&&l2<=h;i++)
{
if(a[l1]<a[l2])
{
t[i]=a[l1];
l1++;
}
else
{
t[i]=a[l2];
l2++;
}

}
while(l1<=mid)
{
t[i]=a[l1];
l1++;
i++;
}
while(l2<=h)
{
t[i]=a[l2];
l2++;
i++;
}
for(i=l;i<=h;i++)
{
a[i]=t[i];
}
return;

}
OUT PUT: