Table of Contents

Vocabulary

Minimum Spanning Trees Subgraph Acyclical Spanning Kruskal’s Algorithm Quick Union

What Are Minimum Spanning Trees?

<aside> 💡 Minimum Spanning Trees (MSTs) are a subset of an undirected graph or subgraph written as $T(V’ E’)$ with the following properties:

1. T must be connected meaning there must be a path between every node.
2. Spanning Trees are acyclical. There are no paths between a node and itself using unique edges.
3. For a subgraph to be deemed spanning, it must contain all of the same nodes as the original graph. In other words, $V’ = V.$

</aside>

Minimum Spanning Tree Example

<aside> 💡 Given a weighted graph, $G(V, E, w)$, where $w$ is a function in the real rumbers ($w(e) \isin \mathbb{R}^+$) and e is in the edge set ($e \isin E$), find a minimum spanning tree such that the edges of this tree have minimal weights.

</aside>

Kruskal’s Algorithm With Fast Find

<aside> 💡 The idea of the Kruskal’s Algorithm to create an MST is to order the edges of a graph by its weight and keep adding edges as long as no cycle is created or until $|V-1|$ since we want edges with small weights but to ensure the MST is acyclical. This algorithm will utilizes the Union Find data structure to avoid cycles. We will use Union Find to check if nodes IDs are not the same. If they aren’t then we will union them.

</aside>

Kruskals(Graph(V, E)) {
		A = {} //empty set
		for each (v in V) {
			make_set(v);
		}
	
		sort E from lowest weights to heighest
		
		for each((u,v) in E) {
			if(find(u) != find(v)) {
				A = A U {u,v};
				union(u,v);
			}
		}
		return A;
}

Kruskal’s Algorithm Example