Untitled
unknown
plain_text
10 months ago
2.0 kB
8
Indexable
#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; } #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; }
Editor is loading...
Leave a Comment