this algo is without using priority queue
| 19 | |
| 20 | // this algo is without using priority queue |
| 21 | void prims_algo1(vector<pair<int, int>> vec[], int v) |
| 22 | { |
| 23 | // one array for checking whether included in mst or not |
| 24 | // second array for distance computation |
| 25 | |
| 26 | vector<bool> mst(v, false); |
| 27 | vector<int> dist(v, INT_MAX); |
| 28 | |
| 29 | // int ans = 0; |
| 30 | |
| 31 | int source = 0; |
| 32 | dist[source] = 0; |
| 33 | |
| 34 | for (int i = 0; i <= v - 1; i++) |
| 35 | { |
| 36 | // finding minimum edge which includes one non added node |
| 37 | int pos = -1; // index of node which is not yet included in MST and is minimum |
| 38 | |
| 39 | // cout << "dist: array: " << endl; |
| 40 | // for (int j = 0; j < dist.size(); j++) |
| 41 | // { |
| 42 | // cout << dist[j] << " "; |
| 43 | // } |
| 44 | // cout<<"mist array: "<<endl; |
| 45 | // for(int j = 0;j<mst.size();j++) { |
| 46 | // cout<<mst[j]<<" "; |
| 47 | // } |
| 48 | // cout<<endl; |
| 49 | // cout << endl; |
| 50 | for (int j = 0; j < dist.size(); j++) |
| 51 | { |
| 52 | if ((dist[j] < dist[pos] && mst[j] == false) || pos == -1 && mst[j] == false) |
| 53 | { |
| 54 | pos = j; |
| 55 | // cout<<"pos: "<<pos<<" "; |
| 56 | } |
| 57 | } |
| 58 | |
| 59 | mst[pos] = true; |
| 60 | |
| 61 | // cout<<endl; |
| 62 | |
| 63 | // ans += dist[pos]; |
| 64 | for (int j = 0; j < vec[pos].size(); j++) |
| 65 | { |
| 66 | int adjacent = vec[pos][j].first; |
| 67 | |
| 68 | if (dist[adjacent] > vec[pos][j].second && mst[adjacent] == false) |
| 69 | { |
| 70 | dist[adjacent] = vec[pos][j].second; |
| 71 | } |
| 72 | } |
| 73 | } |
| 74 | |
| 75 | int ans = 0; |
| 76 | for (int i = 0; i < dist.size(); i++) |
| 77 | { |
| 78 | ans += dist[i]; |