Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <queue>
- using namespace std;
- int p[9],k[9],t[9],i,j;
- int g[9][9] = {
- {0,4,0,0,0,0,0,8,0},
- {4,0,8,0,0,0,0,11,0},
- {0,8,0,7,0,4,0,0,2},
- {0,0,7,0,9,14,0,0,0},
- {0,0,0,9,0,10,0,0,0},
- {0,0,4,14,10,0,2,0,0},
- {0,0,0,0,0,2,0,1,6},
- {8,11,0,0,0,0,1,0,7},
- {0,0,2,0,0,0,6,7,0},
- };
- int Find_min()
- {
- int m = 999999,index;
- for(i=0;i<9;i++)
- {
- if(k[i]<m && t[i] == 0)
- {
- m = k[i];
- index = i;
- }
- }
- return index;
- }
- int main()
- {
- int u,cost=0;
- for(i=0;i<9;i++)
- {
- for(j=0;j<9;j++)
- printf("%d\t", g[i][j]);
- printf("\n");
- }
- for(i=0;i<9;i++)
- {
- p[i] = -1;
- k[i] = 999999;
- t[i] = 0;
- }
- k[0] = 0;
- for(j=0;j<9;j++)
- {
- u = Find_min();
- t[u] = 1;
- for(i=0;i<9;i++)
- {
- if(g[u][i] < k[i] && g[u][i] !=0 && t[i] != 1)
- {
- p[i] = u;
- k[i] = g[u][i];
- }
- }
- }
- printf("\n Parent:\t\t\t");
- for(i=0;i<9;i++)
- printf("%d\t",p[i]);
- printf("\n Key Value:\t\t\t");
- for(i=0;i<9;i++)
- {
- printf("%d\t",k[i]);
- cost += k[i];
- }
- printf("\n Tree Status:\t\t\t");
- for(i=0;i<9;i++)
- printf("%d\t",t[i]);
- printf("\n Total Cost:\t %d",cost);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement