To implement spanning tree using dijkstra's algorithm

#include<stdio.h>

 main()
 {
  int node[50],pred[50],dist[50],status[50],path[50];
  int n,source,dest,adj[50][50],i,j,k,x,temp;
  int infinity=10000;
  system("clear");
  printf("Enter the number of nodes :");
  scanf("%d",&n);
  printf("Enter source node : ");
  scanf("%d",&source );
  printf("Enter the destination node : ");
  scanf("%d",&dest);
  if(source==dest)
  {
   printf("Source and destination are same");
  }
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
   {
    printf("Destination of %dth node to %d th node: ",i,j);
    scanf("%d",&adj[i][j]);
   }
   pred[i]=0;
   status[i]=0;
   dist[i]=infinity;
   node[i]=i;
  }
  dist[source]=0;
  temp=source;
  status[source]=1;
  for(x=1;x<=n,x++)
  {
   for(j=1;j<=n;j++)
    if((adj[source][j]!=0) && (status[j]==0))
    {
     pred[j]=node[source];
     dist[j]=dist[source]+adj[source][j];
    }
   infinity=10000;
   for(k=1;k<=n;k++)
      if(status[k]==0)
    if(dist[k]<infinity)
    {
     infinity=disk[k];
     source=node[k];
    }
   if(source==dest)
    break;
   else
   {
    status[source]=1;
   }
  }
  path[1]=dest;
  k=2;
  for(i=1;i<n;i++)
  {
   path[k]=pred[dest];
   dest=pred[dest];
   k++;
   if(dest==temp)
    break;
  }
  printf("Shortest path is");
  for(k=i+1;k>=1;k++)
   printf("-->%d",path[k]);
  printf("\n");
 }

/*---------------------------------------------------------------------------------------------------------------------
 
   OUTPUT
        --------
   Enter the number of nodes : 3
  Enter the source node : 1
  Enter the destination node : 2
  Destination of 1th node to 1th node:4
  Destination of 1th node to 2th node:20   
  Destination of 1th node to 3th node:3   
  Destination of 2th node to 1th node:2   
  Destination of 2th node to 2th node:4   
  Destination of 2th node to 3th node:4   
  Destination of 3th node to 1th node:1   
  Destination of 3th node to 2th node:2   
  Destination of 3th node to 3th node:2
  Shortest Path is: -->1-->3-->2

To implement minimum spanning tree using Kruskal's algorithm

#include<stdio.h>
    struct graph
    {
        int u,v,wt,select;
    }x[30];
    int n1,n2,rootn1,rootn2,mincost;
    void sort(struct graph x[30],int n)
    {
        struct graph temp;
        int i,j;
        for(i=1;i<=n;i++)
        {
            for(j=i;j<=n;j++)
            {
                if(x[j],wt>x[j+1],wt)
                {
                    temp=x[j];
                    x[j]=x[j+1];
                    x[j+1]=temp;
                }
            }  
        }
    }
        main()
    {
        int w,k=1,n,c=0,i,j;
        printf("\n\tEnter the number of nodes");
        scanf("%d",&n);
        printf("\n\t\tEnter the weights\n");
        scanf("%d",&n);
        printf("\n\tEnter the weights\n");
        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                printf("\t\t\t\t%d->%d = ",i,j);
                scanf("%d",&w);
                if(w>0)
                {
                    x[k],u=i;
                    x[k],v=j;
                    x[k],select=0;
                    x[k],wt=w;
                    k++;
                }
            }
        }
    sort(x,k);
    printf("\n\t\tMinimal spanning tree is : ");
    for(i=1;i<=k;i++)
    {
        if(c==n)
           break;
        n1=x[i],u;
        n2=x[i],v;
        while(n1>0||n2>0)
        {
            if(n1>0)
            {
                rootn1=n1;
                n1=father[n1];
            }
            else
            {
                rootn2=n2;
                n2=father[n2];
            }
        }
        if(rootn1!=rootn2)
        {  
            father[rootn2]=rootn1;
            x[i],select=1;
            printf("\n\t\t\t%d->%d=%d",x[i],u,x[i],v,x[i],wt);
            mincost+=x[i],wt;
            c++;
        }
    }
    printf("\n\t\tMinimum cost =%d",mincost);
    return(0);
}
/*
 ----------------------------------------------------------------------------------------------
        OUTPUT
        ------
    Enter the number of nodes: 4
    Enter the weights
         1->2=2
         1->3=3
         1->4=1
         2->3=2
         2->4=5
         3->4=6
    Minimal spanning tree is:
            1->4=2
         1->2=2
         2->3=2
    Minimal cost=5
----------------------------------------------------------------------------------------------

program to implement priority queue

/*program to implement priority queue*/
#include<stdio.h>
struct node
{
    int data,prio;
    struct node *link;
  
}*nw,*p,*temp,*front=NULL;
void insert()
{
    struct node *temp;
    nw=malloc(sizeof(struct node));
    printf("enter the data");
    scanf("%d",&nw->data);
    printf("enter the priority of the item");
    scanf("%d",&nw->prio);
    nw->link=NULL;
    if(front==NULL||nw->prio<front->prio)
    {
        nw->link=front;
        front=nw;
    }
    else
    {
        temp=front;
        while(temp->link!=NULL && temp->link->prio<=nw->prio)
            temp=temp->link;
        nw->link=temp->link;
        temp->link=nw;
    }
}
void disp()
{
    p=front;
    if(front==NULL)
        printf("queue underflow");
    else
    {
        printf("the data with its priority ");
        while(p!=NULL)
        {
            printf("%d-%d->",p->data,p->prio);
            p=p->link;
        }
    }
}
void del()
{
    if(front==NULL)
        printf("queue underflow");
    else
    {
        temp=front;
        front=front->link;
        printf("the deleted element is %d",temp->data);
        free(temp);
    }
}
void main()
{
    int ch,s;
    do
    {
        printf("select your choice\n");
        printf("1.insert\n");
        printf("2.delete\n");
        printf("3.display\n");
        printf("4.exit\n");
        printf("enter your choice:");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1:insert();break;
            case 2: del();break;
            case 3: disp();break;
            case 4: exit(0);
            default: printf("invalid choice");
        }
    }while(ch!=4);
}      

................................OUTPUT....................  
select your choice
  1.insert
  2.delete
  3.display
  4.exit
  enter your choice1
  enter the data9
  enter the priority of the item1
  select your choice
  1.insert
  2.delete
  3.display
  4.exit
  enter your choice1
  enter the data5
  enter the priority of the item3
  select your choice
  1.insert
  2.delete
  3.display
  4.exit
  enter your choice8
  invalid choice
 select your choice
  1.insert
  2.delete
  3.display
  4.exit
  enter your choice1
  enter the data4
  enter the priority of the item2
  select your choice
  1.insert
  2.delete
  3.display
  4.exit
  enter your choice3
  the data with its priority 9-1->4-2->5-3->
  select your choice
  1.insert
  2.delete
  3.display
  4.exit
  enter your choice2
  the deleted element is 9
       

program to implement binary search

/*program to implement binary search*/
#include<stdio.h>
void sort(int a[],int n)
{
    int i,j,temp;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
}
int binsearch(int a[],int n)
{
    int item,beg,mid,end,i;
    printf("the sorted list is\n");
    sort(a,n);
    for(i=0;i<n;i++)
        printf("%d",a[i]);
    printf("\n");
    printf("enter the element to be searched:");
    scanf("%d",&item);
    beg=0;
    end=n;
    while(beg<=end)
    {
        mid=(beg+end)/2;
        if(a[mid]==item)
            return mid+1;
        else if (a[mid]<item)
            beg=mid+1;
        else
            end=mid-1;
    }

}
main()
{
    int a[20],i,size,loc;
    printf("enter the size of the array");
    scanf("%d",&size);
    printf("enter the elements");
    for(i=0;i<size;i++)
        scanf("%d",&a[i]);
    loc=binsearch(a,size);
    if(loc==0)
        printf("element is not found");
    else
        printf("element is found at the location:%d",loc);
}
...........................OUTPUT.............
enter the size of the array   
5
enter the elements
1
9
5
7
6
the sorted list is
15679
enter the element to be searched:.6
element is not found


enter the size of the array
5
enter the elements
9
4
6
7
1
the sorted list is
14679
enter the element to be searched:6
element is found at the location:3

program to find shortest path of the graph using floyd warshell algorithm

//*floyd*//




#include<stdio.h>
#define maxval 999
int a[10][10],i,j,k,n;

void read()
{
    printf("\nENTER THE SIZE OF MATRIX:");
    scanf("%d",&n);
    printf("\nENTER THE ELEMENTS OF MATRIX:");
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);
}
void print()
{
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        printf("%d",a[i][j]);
        printf("\n");
    }
}
void convert()
{
    for(i=0;i<=n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(a[i][j]==0 && i!=j)
                a[i][j]=maxval;
            else   
                a[i][j]=a[i][j];
        }
    }
}
void shortpath()
{
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            for(k=0;k<n;k++)
            {
                if(a[j][i]+a[i][k]<a[j][k])
                    a[j][k]=a[j][i]+a[i][k];
                else
                    a[j][k]=a[j][k];
            }
        }
    }   
}
main()
{
    read();
    convert();
    printf("\nAFTER REPLACING ZEROS BY MAX VALUE\n");
    print();
    shortpath();
    printf("\nSHORTEST PATH MATRIX\n");
    print();
}