**Table of Contents**show

Spanning Tree concept in Computer science is related to the Graph Data Structures, so do not confuse it with trees.

A Spanning Tree is a subgraph or subset of a Graph G which contain all the vertices of the Graph G with the minimum number of edges. A graph can have more than one spanning tree and all the spanning trees of a graph must have all the vertices of that graph.

As we know that tree data structure does not form a closed-loop or cycle so does spanning tree, all the spanning trees of a graph should not form a closed loop or cyclic structure.

## Spanning Tree

When we design a spanning tree of a graph, that tree must contain all the vertices of the graph. We can also define a spanning tree as follow, “*a spanning tree is a connected graph G with all the vertices of G, that have a minimum number of edges and does not form a cyclic structure*”

**Example:**

GraphX / \ / \ / \ Y---------ZSpanning TreesX \ \ \ Y---------Z X / \ / \ / \ Y Z X / / / Y---------Z

We have a formula which can calculate the maximum number of spanning trees a complete graph could have.

Suppose we have a complete undirected graph with node n so the maximum number of spanning trees of this graph would have **n ^{n-2 }**where n is the total number of nodes or vertices present in the graph.

In the above example, we have a complete undirected graph with vertices **X, Y **and **Z, **which mean it has 3 vertices so the total number of spanning trees that could be formed from it are **3 ^{3-2}**

**= 3.**

**Properties of a Spanning Tree**

As we can form more than one spanning tree from a graph, so while constructing a spanning tree we need to take care of some properties.

- We can form a spanning tree from a connected graph.
- The spanning-tree which is formed from a graph should have all the vertices of the Graph.
- Like a tree, a spanning tree does not form a cyclic structure.
- If we remove an edge from a spanning tree, it would make the graph disconnected which is also known as minimally connected
- If we add an edge in the spanning tree it would make the graph cyclic.
- A spanning tree can have
**n-1**number of edges where n is the number of nodes or vertices present in the graph. - We can only form
**n**number of spanning trees from a complete disconnected graph.^{n-2 }

**Real-world Applications of Spanning Tree**

There are many applications of Spanning tree and all of those are used to reduce the cost of a cluttered network.

- Many pathfinding algorithms such as Dijkstra’s Algorithms and A* search algorithm, build spanning tree to solve the problem
- To minimize the cost of a power network, for wiring connections, piping, automatic speech recognition we use spanning tree.
- For internet and many other telecommunication networks transmission link we use spanning tree.
- To find the shortest path while searching for a specific result on the internet.

**Minimum Spanning Tree**

In the graph, we have weighted graphs, in which a number or weight associated with every edge, the weight signifies the expense or cost of edge from one vertex to another. A minimum spanning tree is a spanning tree of a graph with minimum total weight.

For example:

Weighted GraphX / \ 10/ \20 / \ Y---------Z 30Spanning TreesX \ \20 \ Y-------Z 30 X / \ 10/ \ 20 / \ Y Zminimum spanning treeX / 10/ / Y---------Z 30

**Algorithms of Minimum Spanning Tree**

There are two basic and most important spanning tree algorithms:

- Kruskal’s Algorithm
- Prim Algorithm

**You may be also interested in:**