Minimal Spanning Trees

Introduction

After all that discussion about efficiency, the last subtopic in this chapter is the Minimal Spanning Tree. What is it, really? What is it for and how does it work? 

Buckle up, buddies, this is going to get a lot more confusing. Worry not, though, we’re here to guide you all!

One thing to remember is that this is also a part of efficiency. Minimal Spanning Tree, also known as Minimum Spanning Tree, is a graph not unlike the ones used in the shortest path and backward induction. Before we go deeper, we have to learn the different terms related to this.

1. Network

A network is a set of these so-called “nodes”, also known as vertices, that are connected with one another 

2. Vertices

These are the connecting points of the edges, also called a vertex

3. Edge 

Edges are the lengths that connect one vertex to another

4. Tree

A tree is a graph that is connected by vertices and edges and has no cycles, which means it is not a closed path

5. Spanning Tree

A spanning tree is the representation of the connections of the vertices that also have no cycles

6. Minimal Spanning Tree

A minimal or minimum spanning tree is a spanning tree that takes the most optimal path, which usually is the path where the edges have the smallest weight

The Algorithms of Minimal Spanning Tree

Kruskal's Algorithm

In this algorithm, the graphs are sorted into ascending order. It picks the smallest-weighted edge first before moving to the next smallest one that does not form a cycle, all up until it forms a minimal spanning tree.

Prim's Algorithm

In this algorithm, it starts with a chosen vertex and moves on in an adjacent manner. The goal is to make sure that two vertices are connected, so the next edge that must be taken is an edge that is next to a connected node.

Watch the video below to see how to get the different spanning trees using the two different algorithms.