12346
#include<stdio.h> #include<time.h> int i,j,k,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\tImplementation of Kruskal's algorithm\n"); printf("\nEnter the no. of vertices:"); scanf("%d",&n); printf("\nEnter the cost 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; } } printf("The edges of Minimum Cost Spanning Tree are\n"); clock_t start=clock(); 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("%d edge (%d,%d) =%d\n",ne++,a,b,min); mincost +=min; } cost[a][b]=cost[b][a]=999; } printf("\n\tMinimum cost = %d\n",mincost); clock_t end=clock(); printf("Start time is %lf\n",(double)start); printf("End time is %lf\n",(double)end); printf("Total time is %lf\n",(double)(end-start)); } 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; } 2 #include<stdio.h> #include<time.h> int visited[10]={0}, cost[10][10], min, mincost=0; int i,j,ne=1, a, b, u, v;; int main() { int num; printf("\n\t\t\tPrim's Algorithm"); printf("\n\nEnter the number of nodes= "); scanf("%d", &num); printf("\nEnter the adjacency matrix\n\n"); for(i=1; i<=num; i++) { for(j=1; j<=num; j++) { scanf("%d", &cost[i][j]); if(cost[i][j]==0) cost[i][j]=999; } } clock_t start=clock(); visited[1]=1; while(ne < num) { for(i=1,min=999;i<=num;i++) for(j=1;j<=num;j++) if(cost[i][j]< min) if(visited[i]!=0) { min=cost[i][j]; a=u=i; b=v=j; } printf("\n Edge %d:(%d - %d) cost:%d",ne++,a,b,min); mincost=mincost+min; visited[b]=1; cost[a][b]=cost[b][a]=999; } printf("\n\n\n Minimun cost=%d",mincost); clock_t end=clock(); printf("\nStart time is %lf\n",(double)start); printf("End time is %lf\n",(double)end); printf("Total time is %lf\n",(double)(end-start)); return 0; } 3 #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,u,v,i,j;; printf("\n Enter the number of vertices:"); scanf("%d",&n); printf("\n Matrix of input data:\n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) scanf("%d",&p[i][j]); if(p[i][j]==0) p[i][j]=999; } floyds(p,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]); } } b #include<stdio.h> int max(int, int); void warshal(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++) p[i][j] = max(p[i][j], p[i][k] && p[k][j]); } int max(int a, int b) { if (a > b) return (a); else return (b); } void main() { int p[10][10] = { 0 }, n, e, u, v, i, j; printf("\n Enter the number of vertices:"); scanf("%d", &n); printf("\n Enter the Matrix of input data: \n"); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) scanf("%d", &p[i][j]); } warshal(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"); } } 4 #include<stdio.h> int main () { int n,a[20][20],i,j,min,u,v,s[10],d[10],k; printf ("Enter the number of vertices\n"); scanf("%d",&n); printf ("Enter adjacency matrix\n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&a[i][j]); } } printf("Enter source vertex\n"); scanf("%d",&v); for(i=1;i<=n;i++) { s[i]=0; d[i]=a[v][i]; } d[v]=0; s[v]=1; for(k=2;k<=n;k++) { min=999; for(i=1;i<=n;i++) { if(d[i]<min && s[i]==0) { min=d[i]; u=i; } } s[u]=1; for(i=1;i<=n;i++) { if(s[i]==0) { if(d[i]>d[u]+a[u][i]) { d[i]=d[u]+a[u][i]; } } } } for(i=1;i<=n;i++) { printf("%d---->%d=%d\n",v,i,d[i]); } } 6 #include<stdio.h> int w[10],p[10],n; int max(int a,int b) { return a>b?a:b; } int knap(int i,int m) { if(i==n) return w[i]>m?0:p[i]; if(w[i]>m) return knap(i+1,m); return max(knap(i+1,m),knap(i+1,m-w[i])+p[i]); } int main() { int m,i,max_profit; printf("\nEnter the no. of objects:"); scanf("%d",&n); printf("\nEnter the knapsack capacity:"); scanf("%d",&m); printf("\nEnter profit followed by weight:\n"); for(i=1;i<=n;i++) scanf("%d %d",&p[i],&w[i]); max_profit=knap(1,m); printf("\nMax profit=%d",max_profit); return 0; }
Leave a Comment