kruskal_demo.cpp

// 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;
}