Kruskal algorithm implementation in C++ using STL

Question

I am trying to implement Kruskal algorithm in C++. I followed instructions from a youtube video, where vectors are used. Though the code is shown running accurately in the video, same code doesn't even compile in my PC. I cannot figure out the problem. Here's the code: #include #include using namespace std;

struct Edge{
char vertex1;
char vertex2;
int weight;
Edge(char v1, char v2, int w):vertex1(v1),vertex2(v2),weight(w){}
};

struct Graph
{
vector<char> vertices;
vector<Edge> edges;
};

unordered_map<char,char> PARENT;
unordered_map<char, int> RANK;

char Find(char vertex){
if(PARENT[vertex]==vertex)
    return PARENT[vertex];
else
    return Find(PARENT[vertex]);
}

void Union(char root1, char root2)
{
if(RANK[root1]>RANK[root2]){
    PARENT[root2]=root1;
}
else if(RANK[root2]>RANK[root1]){
    PARENT[root1]=root2;
}
else{
    PARENT[root1]=root2;
    RANK[root2]++;
}
}

void MakeSet(char vertex){
PARENT[vertex] = vertex;
RANK[vertex] = 0;
}

void Kruskal(Graph& g)
{
vector<Edge> A;
for(auto c: g.vertices){
    Makeset(c);
}
sort(g.edges.begin(),g.edges.end(), [](Edge x, Edge y)
{return x.weight<y.weight;});

for(Edge e: g.edges){
    char root1 = Find(e.vertex1);
    char root2 = Find(e.vertex2);
    if(root1!=root2){
        A.push_back(e);
        Union(root1, roo2);
    }
}

for(Edge e: A){
    cout << e.vertex1 << "----" << e.vertex2 << " " e.weight << endl;
}
}

int main()
{
char t[]={'a','b','c','d','e','f'};

Graph g;
g.vertices = vector<char>(t,t+sizeof(t)/sizeof(t[0]));

char sv,ev;
int wt;
while(!EOF){
    cin >> sv >> ev >> wt;
    g.edges.push_back(Edge(sv,ev,wt));
}

Kruskal(g);

return 0;
}

Answer 1

There are a few header files you need to include in your code:

1. unordered_map to use the unordered_map STL. Moreover, you can use it only in C++11 and C++14.
2. vector to use the vector STL.
3. algorithm to use the inbuilt sort() function.

A few more bugs:

1. The name of the function is MakeSet(), and you're calling it using Makeset()
2. You have used roo2 instead of root2 in your for(Edge e: g.edges){} loop
3. The cout statement in your for(Edge e: A){} loop is not syntactically correct.