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.
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 ”
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: