Spanning Tree in Data Structure

In this article, we are going to discuss the Spanning tree. This is one of the most important topics of data structure. First, we will study what is an undirected graph and a connected graph for a better understanding of the Spanning tree in Data Structures.

Undirected Graph

An undirected graph is a graph where the edges do not have a specific direction, meaning they can be traversed in both directions. The edges are bidirectional. This means that if there is an edge connecting vertex A to vertex B, it is also possible to travel from vertex B to vertex A.
It is important to note that in contrast, a directed graph is a graph where the edges have a specific direction and can only be traversed in that direction.

Connected Graph

A connected graph is a graph where there is a path between any two vertices. This means that for any two vertices in the graph, there is a sequence of edges that can be traversed to go from one vertex to the other.
In contrast, a disconnected graph is a graph where there is no path between some pairs of vertices, meaning that it is composed of two or more disconnected subgraphs.

Spanning tree

A spanning tree is a subgraph of an undirected, connected graph that includes all the vertices of the graph with a minimum possible number of edges. If a vertex is missing, it is not considered a spanning tree. The edges in a spanning tree may or may not have weights assigned to them.

The total number of spanning trees that can be formed from a complete graph with n vertices is equal to n(n-2). This can be calculated by using the formula where n is the number of vertices in the graph.

For instance, if the complete graph has 4 vertices, the maximum number of possible spanning trees is equal to 4(4-2) = 16. Therefore, it is possible to form 16 spanning trees from a complete graph with 4 vertices.

Its important to note that this is true for undirected graphs, directed graphs have different numbers of spanning trees can be created.

Its important to note that the above statement about the total number of spanning trees that can be created from a complete graph is only true for undirected graphs. In directed graphs, the total number of spanning trees that can be created from a complete graph is different.

In general, the concept of a spanning tree is useful when we want to have a simplified version of a graph while preserving its connectivity, it allows us to have a reduced representation of a complex network, reducing the number of edges while keeping the information about the connectivity between the vertices.

Example of a Spanning Tree
We can learn in detail about spanning trees by taking the following examples

Normal graph

Let the original graph be:

Given below are the possible spanning trees generated from the given graph:

Minimum Spanning Tree

In a minimum-spanning tree, the sum of the edges of the tree is the minimum possible value

Example of a Spanning Tree
We can understand the spanning tree by taking the following the example
The initial graph is:

Weighted graph

The possible spanning trees from the above graph are:

The minimum spanning tree from the above spanning trees is:

Minimum Cost Subgraph:

For all possible spanning trees, the minimum spanning tree must have the minimum weight possible. However, there may be other spanning trees with the same weight as the minimum-spanning tree, and those can also be considered Minimum Spanning Trees.

Minimum Cost Edge:

If the minimum cost edge of a graph is unique, it will be included in any Minimum Spanning Tree. For example, in the given figure, the edge AB (of least weight) is always included in MST.
If a new edge is added to the spanning tree, it will form a cycle because every spanning tree is minimally acyclic. In the given figure, adding edge AD or BC to the resulting MST would create a cycle.
The spanning tree is minimally connected, meaning if any edge is removed from the spanning tree, it will disconnect the graph. In the given figure, if any edge is removed from the resulting MST, it would disconnect the graph.

Algorithms for finding Minimum Spanning Trees include Kruskals and Prims algorithms.
The concept of MSTs was first introduced by Kruskal in 1956 and later by Prim in 1957. These algorithms have been developed to find the MST of a given graph.

Kruskals Algorithm

Kruskals algorithm starts by sorting all the edges of the graph in increasing order of their weights. Then, it takes each edge one by one and checks if adding the edge would create a cycle. If it doesn’t, the edge is added to the MST. This process is repeated until all the vertices of the graph are included in the MST.

Prims Algorithm

Prim’s algorithm, on the other hand, starts with an arbitrary vertex of the graph and adds to the MST all edges connecting the vertices that are already included in the MST to the vertices that are not yet included but have the minimum weight. This process is repeated until all the vertices are included in the MST.

Both Kruskals and Prims algorithms are used to find the MST of a graph. However, Kruskals algorithm is mainly used for graphs that are sparse, meaning the number of edges is much less than the number of vertices, and Prims algorithm is used for dense graphs, where the number of edges is close to the number of vertices.

In addition to MSTs, there are also other types of spanning trees such as the Maximum Spanning Tree (MaST) and the Shortest Path Tree (SPT). A MaST is a spanning tree with the largest possible total edge weight and SPT is a spanning tree that is used to find the shortest path from a specific vertex to all the other vertices in the graph.

Spanning trees are used in various fields such as computer networks, transportation systems, and image processing. In computer networks, spanning trees are used to create a loop-free topology, preventing network loops, and reducing the number of broadcast messages. In transportation systems, they are used to plan the most efficient routes, and in image processing, they are used to simplify the topology of a binary image while preserving its shape and connectivity.

Conclusion
spanning trees are a crucial concept in graph theory with many applications in various fields. The Minimum Spanning Tree (MST) is an important type of spanning tree that is used to find the subgraph with the smallest possible total edge weight. Kruskals and Prims algorithms are widely used to find the MST of a given graph. Other types of spanning trees such as Maximum Spanning Tree (MaST) and Shortest Path Tree (SPT) also have their own unique applications and uses.

Leave a Reply

Your email address will not be published. Required fields are marked *