# 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.