Skip to content

Instantly share code, notes, and snippets.

@melvincabatuan
Last active January 26, 2021 21:48
Show Gist options
  • Save melvincabatuan/09ac7a146764237eac99703ba4bf2d9a to your computer and use it in GitHub Desktop.
Save melvincabatuan/09ac7a146764237eac99703ba4bf2d9a to your computer and use it in GitHub Desktop.
// kruskal_demo.cpp by Bo Qian
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm> // sort
struct Edge {
char node1;
char node2;
int weight;
Edge(char u, char v, int w):node1(u), node2(v), weight(w){}
};
struct Graph {
std::vector<char> nodes;
std::vector<Edge> edges;
};
// Tree-based Disjoint Set Structure
std::unordered_map<char, char> PARENT;
std::unordered_map<char, int> RANK; // record the depths of trees
char find(char node){ // O(depth)
// finds the disjoint set where the element belongs
// set is identified by the root of the tree
if (PARENT[node] == node)
return PARENT[node];
else
return find(PARENT[node]);
}
void Union(char root1, char root2){ // O(1)
// merge two disjoint sets as one
// choose the root of a deeper tree to be the new root
if (RANK[root1] > RANK[root2]){
PARENT[root2] = root1; // set root1 as parent
} else if (RANK[root2] > RANK[root1]){
PARENT[root1] = root2; // set root2 as parent
} else { // if same depth, then the tree grows deeper
PARENT[root1] = root2;
RANK[root2]++;
}
}
void makeSet(char node){
PARENT[node] = node;
RANK[node] = 0;
}
// Kruskal Algorithm
void kruskal(Graph& g){
std::vector<Edge> result;
for (auto c : g.nodes){
makeSet(c);
}
std::sort(g.edges.begin(), g.edges.end(), [](Edge x, Edge y)
{
return x.weight < y.weight;
} // O(E log E)
);
for (Edge e : g.edges){
char root1 = find(e.node1);
char root2 = find(e.node2);
if (root1 != root2){
result.push_back(e);
Union(root1, root2);
}
}
for (Edge e : result){
std::cout << e.node1 << " <==> " << e.node2 << " " << e.weight << std::endl;
}
}
int main(){
char t[] = {'a','b','c','d','e','f'};
Graph G;
G.nodes = std::vector<char>(t, t + sizeof(t)/sizeof(t[0]));
G.edges.push_back(Edge('a','b',4));
G.edges.push_back(Edge('a','f',2));
G.edges.push_back(Edge('f','b',5));
G.edges.push_back(Edge('c','b',6));
G.edges.push_back(Edge('c','f',1));
G.edges.push_back(Edge('f','e',4));
G.edges.push_back(Edge('d','e',2));
G.edges.push_back(Edge('d','c',3));
kruskal(G);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment