Spanning Tree Algorithm

By Mukesh Kumar|Updated : December 12th, 2021

A spanning tree is defined as a subset of the graph which covers all the vertices of the graph with the minimum possible number of edges. A spanning tree never contains a cycle, and it cannot be disconnected.

In this article, we will discuss and understand the spanning tree, the spanning tree properties, the minimum cost spanning tree, and the minimum cost spanning tree algorithms. Let's first start by understanding the meaning of a spanning tree.

Table of Content

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).

Comments

write a comment

FAQs

  • A spanning tree of a graph G with n vertices is a subset of the graph G that contains all the vertices present in the graph originally, without containing a cycle. A graph may have one or more spanning trees.

  • A minimum cost spanning tree for a weighted, connected, and undirected graph G with n vertices is a subset of the graph that contains all the vertices of the graph with minimum edge weights. A minimum spanning tree may not be unique for a graph.

  • For finding the minimum cost spanning tree, there are two well-known greedy algorithms called:

    • Prim's algorithm
    • Kruskal's algorithm

    These algorithms use a different strategy to find the minimum cost spanning tree. In prim's algorithm, the tree is always connected at every step. However, in Kruskal's, at any step of the algorithm, a graph may be connected or disconnected.

  • The time complexity of the minimum cost spanning tree using prim's algorithm for a graph G using binary heap is O(E log V), where E denotes the edges and V denotes the vertices of the graph G. If we implement prim's algorithm using adjacency matrix, then the time complexity becomes O(V2).

  • To find the number of spanning trees possible for a complete graph, we use the formula nn-2, where n is the number of vertices of the complete graph G.

Follow us for latest updates