#include<stdio.h>

int ne=1,min_cost=0;

void main()

{

  int n,i,j,min,a,u,b,v,cost[20][20],parent[20];

  printf("Enter the no. of vertices:");

  scanf("%d",&n);

  printf("\nEnter the cost matrix:\n");

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

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

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

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

  parent[i]=0;

  printf("\nThe edges of spanning tree are\n");

  while(ne<n)

 {

  min=999;

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

  {

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

   {

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

    {

     min=cost[i][j];

     a=u=i;

     b=v=j;

    }

   }

  }

while(parent[u])

u=parent[u];

while(parent[v])

v=parent[v];

if(u!=v)

{

printf("Edge %d\t(%d->%d)=%d\n",ne++,a,b,min);

min_cost=min_cost+min;

parent[v]=u;

}

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

}

printf("\nMinimum cost=%d\n",min_cost); getch();

}

2.Implementation of Prims Algorithm in C:

#include<stdio.h>

int ne=1,min_cost=0;

void main()

{

 int n,i,j,min,cost[20][20],a,u,b,v,source,visited[20];

 clrscr();

 printf("Enter the no. of nodes:");

 scanf("%d",&n);

 printf("Enter the cost matrix:\n");

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

 {

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

  {

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

  }

 }

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

 visited[i]=0;

 printf("Enter the root node:");

 scanf("%d",&source);

 visited[source]=1;

 printf("\nMinimum cost spanning tree is\n");

 while(ne<n)

 {

  min=999;

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

  {

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

   {

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

    {

      if(visited[i]==0)

      continue;

      else

      {

       min=cost[i][j];

       a=u=i;

       b=v=j;

      }

    }

  }

 }

 if(visited[u]==0||visited[v]==0)

 {

  printf("\nEdge %d\t(%d->%d)=%d\n",ne++,a,b,min);

  min_cost=min_cost+min;

  visited[b]=1;

 }

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

}

printf("\nMinimum cost=%d\n",min_cost); getch();

}

3.Implementation of Dijkstra's algorithm in C:

#include<stdio.h>

void dij(int,int [20][20],int [20],int [20],int);

void main()

{

int i,j,n,visited[20],source,cost[20][20],d[20];

clrscr();

printf("Enter no. of vertices: ");

scanf("%d",&n);

printf("Enter the cost adjacency matrix\n");

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

{

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

 {

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

 }

}

printf("\nEnter the source node: ");

scanf("%d",&source);

dij(source,cost,visited,d,n);

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

{

 if(i!=source)

 printf("\nShortest path from %d to %d is %d",source,i,d[i]);

}

}

void dij(int source,int cost[20][20],int visited[20],int d[20],int n)

{

int i,j,min,u,w;

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

{

visited[i]=0;

d[i]=cost[source][i];

}

visited[source]=1;

d[source]=0;

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

{

 min=999;

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

 {

  if(!visited[i])

  {

   if(d[i]<min)

   {

    min=d[i];

    u=i;

   }

  }

 }

}

  //for i visited[u]=1;

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

 {

  if(cost[u][w]!=999 && visited[w]==0)

  {

  if(d[w]>cost[u][w]+d[u])

  d[w]=cost[u][w]+d[u];

  }

  //for w } // for j

 }

}

4.Implementation of Job Sequencing Algorithm in C:

#include <stdio.h>

#define MAX 100

typedef struct Job

{

  char id[5];

  int deadline;

  int profit;

} Job;

void jobSequencingWithDeadline(Job jobs[], int n);

int minValue(int x, int y)

{

  if(x < y) return x;

  return y;

}

int main(void)

{

  //variables

  int i, j;

  //jobs with deadline and profit

  Job jobs[5] =

  {

    {"j1", 2,  60},

    {"j2", 1, 100},

    {"j3", 4,  20},

    {"j4", 3,  40},

    {"j5", 5,  20},

  };

  //temp

  Job temp;

  //number of jobs

  int n = 5;

  //sort the jobs profit wise in descending order

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

  {

    for(j = 0; j <n - i; j++)

    {

      if(jobs[j+1].profit > jobs[j].profit)

       {

	temp = jobs[j+1];

	jobs[j+1] = jobs[j];

	jobs[j] = temp;

      }

    }

  }

  printf("%10s %10s %10s\n", "Job", "Deadline", "Profit");

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

  {

    printf("%10s %10i %10i\n", jobs[i].id, jobs[i].deadline, jobs[i].profit);

  }

  jobSequencingWithDeadline(jobs, n);

  return 0;

}

void jobSequencingWithDeadline(Job jobs[], int n)

{

  //variables

  int i, j, k, maxprofit;

  //free time slots

  int timeslot[MAX];

  //filled time slots

  int filledTimeSlot = 0;

  //find max deadline value

  int dmax = 0;

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

  {

    if(jobs[i].deadline > dmax)

    {

      dmax = jobs[i].deadline;

    }

  }

  //free time slots initially set to -1 [-1 denotes EMPTY]

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

  {

    timeslot[i] = -1;

  }

  printf("dmax: %d\n", dmax);

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

  {

    k = minValue(dmax, jobs[i - 1].deadline);

    while(k >= 1)

    {

      if(timeslot[k] == -1)

      {

	timeslot[k] = i-1;

	filledTimeSlot++;

	break;

      }

      k--;

    }

    //if all time slots are filled then stop

    if(filledTimeSlot == dmax)

    {

      break;

    }

  }

  //required jobs

  printf("\nRequired Jobs: ");

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

  {

    printf("%s", jobs[timeslot[i]].id);

    if(i < dmax)

    {

      printf(" --> ");

    }

  }

  //required profit

  maxprofit = 0;

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

  {

    maxprofit += jobs[timeslot[i]].profit;

  }

  printf("\nMax Profit: %d\n", maxprofit);

}