• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# C Prim's Algorithm

naeem043 Jun 22nd, 2018 (edited) 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <stdio.h>
2. #include <queue>
3.
4. using namespace std;
5. int p[9],k[9],t[9],i,j;
6. int g[9][9] = {
7.     {0,4,0,0,0,0,0,8,0},
8.     {4,0,8,0,0,0,0,11,0},
9.     {0,8,0,7,0,4,0,0,2},
10.     {0,0,7,0,9,14,0,0,0},
11.     {0,0,0,9,0,10,0,0,0},
12.     {0,0,4,14,10,0,2,0,0},
13.     {0,0,0,0,0,2,0,1,6},
14.     {8,11,0,0,0,0,1,0,7},
15.     {0,0,2,0,0,0,6,7,0},
16.
17. };
18.
19. int Find_min()
20. {
21.     int m = 999999,index;
22.     for(i=0;i<9;i++)
23.     {
24.         if(k[i]<m && t[i] == 0)
25.         {
26.             m = k[i];
27.             index = i;
28.         }
29.     }
30.
31.     return index;
32. }
33.
34. int main()
35. {
36.     int u,cost=0;
37.     for(i=0;i<9;i++)
38.     {
39.         for(j=0;j<9;j++)
40.             printf("%d\t", g[i][j]);
41.         printf("\n");
42.     }
43.
44.    for(i=0;i<9;i++)
45.     {
46.         p[i] = -1;
47.         k[i] = 999999;
48.         t[i] = 0;
49.
50.     }
51.     k[0] = 0;
52.
53.   for(j=0;j<9;j++)
54.     {
55.         u = Find_min();
56.         t[u] = 1;
57.         for(i=0;i<9;i++)
58.         {
59.             if(g[u][i] < k[i] && g[u][i] !=0 && t[i] != 1)
60.             {
61.                 p[i] = u;
62.                 k[i] = g[u][i];
63.             }
64.         }
65.     }
66.
67.
68.     printf("\n Parent:\t\t\t");
69.     for(i=0;i<9;i++)
70.         printf("%d\t",p[i]);
71.
72.
73.     printf("\n Key Value:\t\t\t");
74.     for(i=0;i<9;i++)
75.     {
76.         printf("%d\t",k[i]);
77.         cost += k[i];
78.     }
79.
80.
81.     printf("\n Tree Status:\t\t\t");
82.     for(i=0;i<9;i++)
83.         printf("%d\t",t[i]);
84.
85.     printf("\n Total Cost:\t %d",cost);
86.
87.     return 0;
88. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top