Minimum Spanning Tree

Explanation

A minimum spanning tree is the minimum set of edges that connects a weighted graph. Specifically, a minimum spanning tree is a solution to the set of edges where the total edge weight is as small as possible. In this example, the weights of nodes of our graph are the distances between 2 nodes. To show how each algorithm works, the node positions have been randomized.

Prim's algorithm works by choosing a starting node and adding it to an initially empty subset, defined L. Next, we add the edge e{a, b} such that a is a member of L, b is not a member of L, and the weight between a and b is minimized. Add b to L. We repeat this process until all nodes are connected. The algorithm's time complexity is O(n²), where n is the number of nodes in the graph.

Borůvka's algorithm starts by iterating through every node (a single tree), then merging it with the closest tree. Groups of trees (forests) are merged to form larger forests. This process is repeated until all forests are merged into one forest containing all the trees. This algorithm's outer loop runs at O(log n), where n is the number of nodes in the graph.

Nodes are the same as vertices.

More Info