# Least weight set of arcs connecting all vertices

## Concept of a Least Weight Set of Arcs Connecting all Vertices

• Known as the minimum spanning tree (MST), this represents the set of arcs that connects all vertices in a graph without any cycles and with the least total weight.
• Real-world applications of this concept include network design like telecommunications, power grid, and piping systems where it’s essential to connect all nodes at the minimum cost.
• The weight of the spanning tree is represented by the sum of weights of all the arcs in the tree.

## Algorithms for Finding the Minimum Spanning Tree

• Kruskal’s Algorithm and Prim’s Algorithm are the two main algorithms used frequently to solve the minimum spanning tree problem.
• Both these algorithms make use of greedy technique where the next best or local optimum move is chosen at each step with an aim to find the global optimum solution.

## Kruskal’s Algorithm

• This algorithm works by sorting all the edges from the lowest weight to the highest.
• Then it crosses each edge off the list in order, and adds it to the spanning tree, as long as the edge does not create a cycle.
• The algorithm was named after its discoverer, Joseph Kruskal, a mathematician and a computer scientist.

## Prim’s Algorithm

• Prim’s algorithm works by starting with a single vertex and continuously adding the smallest edge that connects the growing tree to a vertex not yet in the tree.
• Conceived by Robert C. Prim in 1957, it’s a way to find a minimum spanning tree in a weighted undirected graph.

## Common Pitfalls and Errors

• Beware of disconnected graphs. Both algorithms fail to give a minimum spanning tree for a graph that is not connected.
• Distinguishing between visited and unvisited vertices is crucial as it saves time and prevents cycles.

## Practical Application and Exercises

• Real-life scenarios such as planning roads between towns or laying down cables can aid in understanding the concept of a minimum spanning tree.
• Doing coding exercises implementing Kruskal’s Algorithm and Prim’s Algorithm can consolidate the learner’s understanding.
• Using contrasting examples to visualise the sequences of the process for both algorithms supports cognitive understanding.