## Spanning Trees:

A spanning tree of a connected, undirected graph is a subgraph that includes all the vertices of the original graph and forms a tree without forming any cycles.

• In other words, a spanning tree is a tree that spans all the vertices of a graph, connecting them together without creating loops or circuits.

• A graph may have more than one spanning tree.

**Note: **A Spanning tree does not exist for a disconnected graph.

• A subgraph T of a connected graph G is called spanning tree of G if T is a tree and T include all vertices of G.

**‣ **The number of spanning trees in a complete graph with N vertices isN^{N-2}**For example**: N=4, then maximum number of spanning tree possible =4^{4-2}= 16

## Applications of A Spanning Tree:

Spanning trees find applications in various fields due to their ability to ensure connectivity, simplify graph structures, and optimize resource usage.

**Here are some specific applications of spanning trees:**

- Network Design
- Circuit Design
- Telecommunication
- Transportation Planning
- Power Distribution Networks

## Minimum Spanning Tree:

A **minimum spanning tree (MST)** of a connected, undirected graph is a subset of the edges of the graph that connects all the vertices of the graph with the minimum total weight.

• The total edge weight is the sum of the weights of all the edges in the spanning tree. Finding the minimum spanning tree is a common problem in graph theory and optimization.

## Algorithms to Find Minimum Spanning Tree of a Graph:

There are several algorithms to find the minimum spanning tree (MST) of a graph. The two primary algorithms are Kruskal’s Algorithm and Prim’s Algorithm.

**Some of them are listed below:**

- Kruskal’s Algorithm
- Prim’s Algorithm
- Boruvka’s Algorithm
- Reverse-Delete Algorithm

## ‣ Kruskal’s Algorithm:

**Kruskal’s Algorithm** is a greedy algorithm used to find a minimum spanning tree in a connected, undirected graph.

• The algorithm operates by repeatedly adding the smallest edge that does not form a cycle with the edges already chosen.

## ‣ Prim’s Algorithm:

**Prim’s Algorithm** is a greedy algorithm used for finding a minimum spanning tree (MST) in a connected, undirected graph.

• Similar to Kruskal’s Algorithm, Prim’s Algorithm builds the minimum spanning tree step by step, always selecting the edge with the minimum weight.