//lab 1

#include<stdio.h>

#include<stdlib.h>

int i,j,a,b,u,v,n,ne=1;

int min ,mincost=0,cost[9][9],parent[9];

int find(int);

int uni(int,int);

void main(){

printf("\n\n\t Implementation of Kruskals alg\n\n");

printf("\n Enter the no of vertices\n");

scanf("%d",&n);

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

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;

printf("\n The edges of min cost spanning tree are\n\n");

while(ne<n)

for(i=1,min=999;i<=n;i++)

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

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

{
 min=cost[i][j];

a=u=i;

b=v=j;

u=find(u);

v=find(v);

if(uni(u,v))

printf("\n %d edge(%d%d)=%d\n",ne++,a,b,min);

mincost+=min;

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

printf("\n \t Minimum cost=%d\n",mincost);

int find(int i){

while(parent[i])

i=parent[i];

return i;

int uni(int i,int j)

if(i!=j)

parent[j]=i;

return 1;

return 0;

}
//lab 2

#include<stdio.h>

int a,b,u,v,n,i,j,ne=1;

int visited[10]={0},min,mincost=0,cost[10][10];

void main()

printf("\n Enter the number of nodes:");

scanf("%d",&n);

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

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;

visited[1]=1;

printf("\n");

while(ne<n)

for(i=1,min=999;i<=n;i++)

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

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

if(visited[i]!=0)

min=cost[i][j];

a=u=i;

b=v=j;
 }

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

printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);

mincost+=min;

visited[b]=1;

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

printf("\n Minimun cost=%d",mincost);

}
//lab 3 a

#include<stdio.h>

int min(int,int);

void floyds(int p[10][10],int n)

int i,j,k;

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

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

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

if(i==j)

p[i][j]=0;

else

p[i][j]=min(p[i][j],p[i][k]+p[k][j]);

int min(int a,int b)

if(a<b)

return(a);

else

return(b);

void main()

int p[10][10],w,n,e,u,v,i,j;;

printf("\n Enter the number of vertices:");

scanf("%d",&n);

printf("\n Enter the number of edges:\n");

scanf("%d",&e);

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

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

p[i][j]=999;

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

printf("\n Enter the end vertices of edge%d with its weight \n",i);

scanf("%d%d%d",&u,&v,&w);

p[u][v]=w;

printf("\n Matrix of input data:\n");

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

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

printf("%d \t",p[i][j]);

printf("\n");

floyds(p,n);

printf("\n Transitive closure:\n");

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

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

printf("%d \t",p[i][j]);

printf("\n");

printf("\n The shortest paths are:\n");

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

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

if(i!=j)

printf("\n <%d,%d>=%d",i,j,p[i][j]);

}}
//lab 3 b

# include <stdio.h>

int n,a[10][10],p[10][10];

void path()

int i,j,k;

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

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

p[i][j]=a[i][j];

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

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

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

if(p[i][k]==1&&p[k][j]==1)

p[i][j]=1;

void main()

int i,j;

printf("Enter the number of nodes:");

scanf("%d",&n);

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

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

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

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

path();

printf("\nThe path matrix is showm below\n");

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

{
for(j=0;j<n;j++)

printf("%d ",p[i][j]);

printf("\n");

}
//lab 4

#include<stdio.h>

#define infinity 999

void dij(int n,int v,int cost[10][10],int dist[100])

int i,u,count,w,flag[10],min;

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

flag[i]=0,dist[i]=cost[v][i];

count=2;

while(count<=n)

min=99;

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

if(dist[w]<min && !flag[w])

min=dist[w],u=w;

flag[u]=1;

count++;

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

if((dist[u]+cost[u][w]<dist[w]) && !flag[w])

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

void main()

int n,v,i,j,cost[10][10],dist[10];

printf("\n Enter the number of nodes:");

scanf("%d",&n);

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

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]=infinity;

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

scanf("%d",&v);

dij(n,v,cost,dist);

printf("\n Shortest path:\n");

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

if(i!=v)

printf("%d->%d,cost=%d\n",v,i,dist[i]);

}
//lab 5

#include<stdio.h>

const int MAX=10;

void fnTopological(int a[MAX][MAX],int n);

int main(void)

int a[MAX][MAX],n;

int i,j;

printf("Topological Sorting Algorithm-\n");

printf("\nEnter the number of vertices:");

scanf("%d",&n);

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

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

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

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

fnTopological(a,n);

printf("\n");

return 0;

void fnTopological(int a[MAX][MAX],int n)

int in[MAX],out[MAX],stack[MAX],top=-1;

int i,j,k=0;

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

in[i]=0;

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

if(a[j][i]==1)

in[i]++;

}
 while(1)

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

if(in[i]==0)

stack[++top]=i;

in[i]=-1;

if(top==-1)

break;

out[k]=stack[top--];

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

if(a[out[k]][i]==1)

in[i]--;

k++;

printf("\n Topological Sorting (JOB SEQUENCE) is :-\n");

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

printf("%d",out[i]+1);

}
//lab 6

#include<stdio.h>

int w[10],p[10],v[10][10],n,i,j,cap,x[10]={0};

int max(int i,int j)

return((i>j)?i:j);

int knap(int i,int j)

int value;

if(v[i][j]<0)

if(j<w[i])

value=knap(i-1,j);

else

value=max(knap(i-1,j),p[i]+knap(i-1,j-w[i]));

v[i][j]=value;

return (v[i][j]);

void main()

int profit,count=0;

printf("\n Enter the number of elements:\n");

scanf("%d",&n);

printf("Enter the profit and weights of the elements\n");

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

{
 printf("For item no %d\n",i);

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

printf("\nEnter the capacity \n");

scanf("%d",&cap);

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

for(j=0;j<=cap;j++)

if((i==0)||(j==0))

v[i][j]=0;

else

v[i][j]=-1;

profit=knap(n,cap);

i=n;

j=cap;

while(j!=0 && i!=0)

if(v[i][j]!=v[i-1][j])

x[i]=1;

j=j-w[i];

i--;

else

i--;

printf("Items included are \n");

printf("Sl.no\t weight \t profit \n");

for(i=1;i<=n;i++)
 if(x[i])

printf("%d \t %d \t %d \n",++count,w[i],p[i]);

printf("Total profit = %d \n",profit);