DAA-Lab-Programs/primsAlgorithm.cpp at master · geeky1Coder/DAA-Lab-Programs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

void primsAlog(vector<vector<int>> graph)
{
    int n = graph.size();

    vector<int> parent(n, -1);
    vector<int> values(n, INT_MAX);
    set<int> vis;

    values[0] = 0;
    vis.insert(0);
    int minEl = INT_MAX;
    int minIdx = 0;

    for (int t = 0; t < (n - 1); ++t)
    {
        int e=0;
        for(auto el:graph[minIdx]){
            if(el!=0&&(values[e]>(el))){
                parent[e]=minIdx;
                values[e]=el;
            }
            e++;
        }

        minEl=INT_MAX;
        minIdx=-1;
        int i = 0;
        for (auto el : values)
        {
            if ((vis.find(i)==vis.end())&&(el < minEl))
            {
                minIdx = i;
                minEl = el;
            }
            i++;
        }

        vis.insert(minIdx);
    }

    int totalWeight=0;
    for (int i = 1; i < n; i++){
            cout<<parent[i]<<" - "<<i<<" \t"<<graph[i][parent[i]]<<" \n";
            totalWeight+=graph[i][parent[i]];
    }

   cout<<"Total weight : "<<totalWeight<<endl;
}

int main()
{
    vector<vector<int>> graph = {{0, 2, 0, 6, 0},
                                 {2, 0, 3, 8, 5},
                                 {0, 3, 0, 0, 7},
                                 {6, 8, 0, 0, 9},
                                 {0, 5, 7, 9, 0}};
    primsAlog(graph);
}