| 89 | }; |
| 90 | |
| 91 | void prims_algo2(vector<pair<int, int>> vec[], int v) |
| 92 | { |
| 93 | vector<bool> mst(v, false); |
| 94 | vector<int> dist(v, INT_MAX); |
| 95 | |
| 96 | dist[0] = 0; |
| 97 | priority_queue<pair<int, int>, vector<pair<int, int>>, mycmp> pq; |
| 98 | pq.push({0, 0}); |
| 99 | |
| 100 | int ans = 0; |
| 101 | |
| 102 | int count = 0; |
| 103 | for (int i = 0; i < v; i++) |
| 104 | { |
| 105 | while (pq.empty() == false && mst[pq.top().first] == true) |
| 106 | { |
| 107 | pq.pop(); |
| 108 | } |
| 109 | pair<int, int> curr = pq.top(); |
| 110 | pq.pop(); |
| 111 | |
| 112 | // cout << "curr.first() " << curr.first << " curr.second() " << curr.second << endl; |
| 113 | |
| 114 | mst[curr.first] = true; |
| 115 | ans += curr.second; |
| 116 | for (int j = 0; j < vec[curr.first].size(); j++) |
| 117 | { |
| 118 | int adjacent = vec[curr.first][j].first; |
| 119 | if (mst[adjacent] == false && dist[adjacent] > vec[curr.first][j].second) |
| 120 | { |
| 121 | pq.push({adjacent, vec[curr.first][j].second}); |
| 122 | } |
| 123 | } |
| 124 | } |
| 125 | cout << "Final answer from algo 2 is : " << ans << endl; |
| 126 | } |
| 127 | |
| 128 | int main() |
| 129 | { |