Tag Archives: Reverse-delete algorithm

Computer Algorithms: Prim’s Minimum Spanning Tree

Introduction

Along with the Kruskal’s minimum spanning tree algorithm, there’s another general algorithm that solves the problem. The algorithm of Prim.

As we already know the algorithm of Kruskal works in a pretty natural and logical way. Since we’re trying to build a MST, which is naturally build by the minimal edges of the graph (G), we sort them in a non-descending order and we start building the tree.

The algorithm of Kruskal
 

During the whole process of building the final minimum spanning tree Kruskal’s algorithm keeps a forest of trees. The number of trees in that forest decreases on each step and finally we get the minimum weight spanning tree.

A key point in the Kruskal’s approach is the way we get the “next” edge from G that should be added to one of the trees of the forest (or to connect two trees from the forest). The only thing we should be aware of is to choose an edge that’s connecting two vertices – u and v and these two shouldn’t be in the same tree. That’s all.

The Kruskal's Tricky Part
 

An important feature of the Kruskal’s algorithm is that it builds the MST just by sorting the edges by their weight and doesn’t care about a particular starting vertex.

In the same time there’s another algorithm that builds a MST – the algorithm of Prim designed by Robert Prim in 1957. Continue reading Computer Algorithms: Prim’s Minimum Spanning Tree

Computer Algorithms: Kruskal’s Minimum Spanning Tree

Introduction

One of the two main algorithms in finding the minimum spanning tree algorithms is the algorithm of Kruskal. Before getting into the details, let’s get back to the principles of the minimum spanning tree.

We have a weighted graph and of all spanning trees we’d like to find the one with minimal weight. As an example on the picture above you see a spanning tree (T) on the graph (G), but that isn’t the minimum weight spanning tree!

A graph and a possible spanning tree
 
Continue reading Computer Algorithms: Kruskal’s Minimum Spanning Tree