Minimum Spanning Trees, Prim’s, Kruskal’s and Round‐ Robin Algorithms

Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subgraph of an undirected graph such that the subgraph spans (includes) all nodes, is connected, is cyclic, and has minimum total edge weight. A single graph can have various different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use it to calculate the total weight of the spanning tree formed.A minimum spanning tree (MST) or minimum weight spanning tree is the one with weight less than or equal to the weight of every other spanning tree. In general, any undirected graph has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.

Applications of MST

• Minimumcost-spanning trees have many applications, some of them are:
  • Building cable networks that join n locations with minimum cost
  • Building a road network that joins n cities with minimum cost
  • Obtaining an independent set of circuit equations for an electrical network
  • In pattern recognition, MSTs can be used to find noisy pixels.

Kruskal's Algorithm

Description
Find the MST by taking the smallest weight in the graph and connecting the two nodes and repeating until all nodes are connected to just one tree. This is done by creating a priority queue using the weights as keys.

Example

Prim's Algorithm

In computer science, Prim's algorithm is a greedy algorithm that finds an MSTfor a weighted undirected graph. This means it finds a subset of the edges that forms tree including every vertex, with the total weight of all the edges in the tree minimized. The algorithm works by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex in terms of weight of the graph.

1. Select any vertex
2. Select the shortest edge connected to that vertex
3. Select the shortest edge connected to any vertex already connected
4. Repeat step 3 until all vertices have been connected

Let

T = a spanning tree containing a single node s;

E = set of edges adjacent to s;

while T does not contain all the nodes{

remove an edge (v,w) of lowest cost from E

if w is already in T, then discard edge (v,w)

else {

add edge (v,w) and node w to T

add to E the edges adjacent to w

}

}

Example:

References

1.https://en.wikipedia.org/wiki/Kruskal's_algorithm

2.https://en.wikipedia.org/wiki/Prim's_algorithm

3. Karumanchi, N. "Data Structures and Algorithms Made Easy"

4. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

5. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”