What is a spanning tree?
A spanning tree is defined as a subset of Graph G that has all the vertices covered with the minimum possible number of edges. Let us suppose a Graph G which has n number of vertices and e number of edges, then:
- Spanning tree T of Graph G contains n vertices and (n-1) edges.
- Spanning tree T has no cycles.
By definition, we can conclude that every undirected, connected graph G has at least one spanning tree. Also, a disconnected graph does not have any spanning tree as all the vertices of the graph cannot be covered.
Spanning Tree Properties
A connected, undirected graph has at least one spanning tree, while a disconnected graph has none. To understand the spanning tree, let us see the properties:
- For a graph, all the possible spanning trees have the same number of vertices and edges.
- A spanning tree never contains a loop or a cycle, which is the property of a tree.
- A graph can have more than one spanning tree.
- A complete graph has maximum nn-2 spanning trees.
What is a Minimum Cost Spanning Tree?
A minimum cost spanning tree abbreviated as MST is a subset of a connected, weighted, and an undirected graph that connects all the vertices of the graph with the minimum possible weight of the edges.
To find the minimum cost spanning tree for a graph, we use two algorithms, namely:
- Prims Minimum Spanning Tree Algorithm
- Kruskal's Minimum Spanning Tree Algorithm
Both the algorithms follow the greedy strategy. We will concisely discuss the above two minimum cost spanning tree algorithms to understand their functioning and work to find the minimum cost spanning tree.
Note: A minimum spanning tree(MST) is not necessarily unique.
Minimum Spanning Tree Prim's Algorithm
To find the minimum cost spanning tree, a greedy approach is used by the prim's algorithm. We keep a priority queue that is filled with all the nodes that have not yet been spanned. Now, we take the value of each of these nodes, which is equal to the minimum weight of the edges that connect these nodes to the partial spanning tree.
The characteristics of the prim's algorithm for minimum cost spanning tree are:
- It can be implemented using a priority queue.
- The (Minimum Spanning Tree) MST generated vertex by vertex.
- The intermediate result of prim's algorithm is always a connected graph.
- The time complexity for Prim's algorithm (using binary heap) is O (|E| log |V|).
- If Prim's algorithm is implemented using an adjacency list, then the time complexity is O(|V|2).
Minimum Spanning Tree Kruskal's Algorithm
Another algorithm used to find the minimum cost spanning tree is Kruskal's algorithm. It also follows the greedy approach. And yields the same result as Prim's algorithm; however, there is a difference in the procedure. Let us see the characteristics of Kruskal's algorithm:
- It follows the greedy approach to compute the minimum spanning tree.
- Kruskal's algorithm computes the minimum spanning tree by considering the edges in increasing order of weight.
- The intermediate result of Kruskal's algorithm may be a connected or disconnected graph.
- It can be implemented using Union find data structure.
- The time complexity for Kruskal's algorithm is O(E logE).