# DSA: Graph- Spanning Tree 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:

``` Graph
X
/   \
/     \
/       \
Y---------Z

Spanning Trees

X
\
\
\
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 n-2 number of spanning trees from a complete disconnected graph.

### 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 Graph
X
/   \
10/     \20
/       \
Y---------Z
30

Spanning Trees

X
\
\20
\
Y-------Z
30

X
/   \
10/     \ 20
/       \
Y         Z
minimum spanning tree

X
/
10/
/
Y---------Z
30```

### Algorithms of Minimum Spanning Tree

There are two basic and most important spanning tree algorithms:

• Kruskal’s Algorithm
• Prim Algorithm

People are also reading: