Spanning Tree

A spanning tree in data structures is a sub-graph, that contains all the vertices of a graph. A spanning tree may or may not be weighted, a spanning tree does not have cycles and it cannot be disconnected. The spanning tree has a minimal set of edges. A single connected graph can have multiple spanning trees.

Graph

A graph can be depicted as a set of vertices connected by edges. The most common types of graphs are as follows:

1. Undirected Graph: This type of graph features bidirectional edges, meaning they don't have a specified direction. It can be viewed as a graph with V vertices and E edges, where each edge connects two distinct vertices.
2. Connected Graph: A connected graph is one in which there is always a path between any two vertices. Another way to express this is that a graph is connected if one can reach any vertex from any other vertex by following edges in either direction.
3. Directed Graph: A graph is labeled as a directed graph if all the edges between nodes or vertices have a specified direction.

What is Spanning Tree?

A spanning tree is a sub-graph that connects all the vertices of the graph with the minimum possible number of edges. Spanning Trees of a given graph G can also be defined as a minimal set of edges that contains all the vertices of G. A spanning tree does not have any cycle and it can never be disconnected. A spanning tree can be weighted or unweighted.

Example of Spanning Tree

A complete undirected graph G can have a maximum n^n-2 number of spanning trees, where n is the number of nodes in a given graph G. Let us Consider a complete graph G with 3 vertices, then the total number of spanning trees this graph can have is 3^(3-2)=3 which are shown in the image below.

In the above picture, we can see that the tree have no cycles and they are minimally connected so they are all the possible spanning trees of 3 vertices for a given graph G.

Properties of Spanning Tree

Let us discuss some properties of a spanning tree.

• All possible spanning trees for graph G have the same number of edges and vertices.
• Spanning trees do not have any cycles.
• A spanning tree is a minimally connected sub-graph, which means if we remove any edge from the spanning tree then it becomes disconnected.
• A spanning tree is a maximally acyclic sub-graph, which means if we add an edge to the spanning tree then it becomes cyclic.
• A connected graph G can have more than one spanning tree.
• A disconnected graph cannot have a spanning tree.
• In the case of a connected graph with N vertices, the number of edges in its spanning tree is equal to N-1.
• To construct a spanning tree for a complete graph, remove E-N+1 edges, where E is the number of edges, and N is the number of vertices.
• Cayley’s Formula states that the total number of spanning trees that a complete graph of n vertices can have is n^(n-2).

Applications of Spanning Tree

Following are a few applications of spanning trees:

• Computer Networking: Spanning trees, especially through protocols like the Spanning Tree Protocol (STP), play a crucial role in optimizing and organizing networks. They ensure efficient data travel without causing loops.
• Electrical Power Systems: Spanning trees assist in identifying the minimum spanning tree, optimizing the distribution of power lines to minimize costs and energy loss.
• Geographic Information Systems (GIS): Spanning trees are used in GIS to design efficient transportation networks, determining the most economical routes for connecting different locations.
• Biology: Spanning trees are employed in biology to model hierarchical structures, such as phylogenetic trees, representing evolutionary relationships among species.

What is Minimum Spanning Tree?

A minimum spanning tree is the spanning tree that has a minimum cost among all the spanning trees. The cost of the spanning tree is the sum of the weights of all the edges in the tree. In real-life situations, this weight can be measured as distance, cost of transportation, manufacturing cost, traffic load, or any arbitrary value denoted by the edges. A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.

For a given graph G, a minimum spanning tree of a graph is unique if the weight of all the edges is distinct. Otherwise, there may be multiple possible minimum spanning trees.

Example of Minimum Spanning Tree

Let us understand the Minimum Spanning Tree with the help of the example below.

Consider a weighted graph G with three vertices as shown in the picture below.

Now let us see some of the spanning trees which are possible with this graph G.

1.

Total Cost=4+5=9

2.

Total Cost=4+7=11

3. Total Cost=7+5=12

From the above three cases, we can see that among all possible spanning trees figure 1 has the minimum cost, So it is the minimum spanning tree among the given spanning trees.

Properties of Minimum Spanning Tree

Let us discuss some properties of a minimum spanning tree.

• A minimum spanning tree connects all vertices in the graph, providing a path between any pair of nodes.
• An MST is acyclic, ensuring it remains a tree without cycles or loops.
• An MST with V vertices (where V is the number of vertices in the original graph) will have exactly V – 1 edges.
• While optimal for minimizing total edge weight, an MST may not be unique.
• The cut property asserts that, for any cut in the original graph (a partition of vertices into two sets), the minimum-weight edge crossing the cut is part of the MST.

Applications of Minimum Spanning Tree

Following are the applications of MSTs:

• Network Design: MSTs contribute to the optimization and efficiency of communication infrastructure in network design. They help establish the most cost-effective and reliable network of cables, particularly in telecommunications, for efficient data transmission.
• Logistics and Transportation Planning: MSTs are utilized in logistics and transportation planning to design the most economical routes for delivery and distribution, thereby minimizing overall costs.
• Circuit Design and Wiring Layout: In circuit design and wiring layout, MSTs assist in minimizing the total length of wires, leading to reduced material and operational expenses.

Minimum Spanning Tree Algorithm

There are two famous algorithms for finding the Minimum Spanning Tree of a graph:

Kruskal’s Algorithm

In Kruskal’s Algorithm, the spanning tree is constructed by adding the edges one by one. Kruskal’s Algorithm is based on the greedy approach because every time we add that edge that has the least weight among all available options.

Algorithm Steps:

1. Sort all the edges of the graph in the increasing order of their weight.
2. Pick the edge with the smallest weight.
3. Check if it forms a cycle with the spanning tree formed so far.
   • Include the current edge if it does not form any cycle.
   • Otherwise discard it.
4. Repeat step 3 until there V-1 edges in the spanning tree, where V is the total number of vertices in the graph.

The Kruskal's algorithm is a Greedy Algorithm. The greedy choice is to pick the smallest weight edge that does not cause a cycle in the MST constructed so far.

To detect if after including the current edge it will form a cycle or not we use the union finds algorithm.

Example

Let us understand the working of Kruskal's Algorithm with an example. Consider a weighted graph G having seven vertices in the picture below.

Now to find the minimum spanning tree using Kruskal's Algorithm, follow the steps below.

1. Choose the edge with the minimum weight.

2. Choose the next shortest edge and add it. We can see from the below picture that the next shortest edge need not be connected with the former one.

3. Choose the next shortest edge that doesn't create a cycle and add it.

4. Choose the next shortest edge that doesn't create a cycle and add it. If there are more than one such edges, choose anyone from them.

5. Choose the next shortest edge that doesn't create a cycle and add it.

6. Repeat step 5 until you a spanning tree.

Here is the C++ implementation of the above approach

Input of Above Code

Output of Above Code

Prim's Algorithm

Like Kruskal’s Algorithm the Prim's Algorithm is also used to find the minimum spanning tree from a graph. In Prim's algorithm, we find the subset of edges that includes every vertex of the graph in such a manner that the sum of the weights of the edges can be minimized. Unlike Kruskal's algorithm, Prim's algorithm treats the nodes as a single tree and keeps on adding new nodes to the spanning tree from the given graph.

Algorithm Steps:

• Initialize:
  • Select an arbitrary starting vertex.
  • Create an empty set to keep track of selected vertices, initially containing only the starting vertex.
  • Create a priority queue (or Min Heap) to store the edges and their weights.
• Repeat until all vertices are included:
  • Select the Minimum Weight Edge:
    • Iterate through all the edges connected to the currently selected vertices.
    • Add all the edges connecting a selected vertex to an unselected vertex to the priority queue.
  • Choose the Minimum Weight Edge:
    • Extract the edge with the minimum weight from the priority queue.
  • Add the Vertex to the MST:
    • Add the destination vertex of the selected edge to the set of selected vertices.
  • Update the Priority Queue:
    • Remove any edges in the priority queue that connect already selected vertices.
• Continue until the MST contains all vertices.

Example Consider a weighted graph G having seven vertices in the picture below.

Now to find the minimum spanning tree using Prim's Algorithm, follow the steps below.

1. Choose any arbitrary vertex , here we are starting from vertex 1 in the given graph G.

2. Choose the shortest edge from this vertex and add it to the spanning tree so formed.

3. Choose the nearest vertex which is not yet included in the solution. In each iteration, we are considering all the respective fringe vertices for a particular vertex.

4. Choose the nearest vertex which is not yet included in the solution and does not form any cycle.

5. Choose the nearest vertex which is not yet included in the solution and does not form any cycle.

6. Repeat the same process until our minimum spanning tree does not have V-1 vertices, where v is the total number of vertices in the in original graph G.

Here is the C++ implementation of the above approach

Output of Above Program

Complexity Analysis

Kruskal's Algorithm

• Adjacency Matrix Representation:
  • Time Complexity: O(V²)
  • Space Complexity: O(V²)
• Adjacency List Representation:
  • Time Complexity: O(ElogE + ELogV)
  • Space Complexity: O(V + E)

Prim's Algorithm

• Adjacency Matrix Representation:
  • Time Complexity: O(V²)
  • Space Complexity: O(V²)
• Adjacency List Representation (Using Min Heap):
  • Time Complexity: O((V + E)logV)
  • Space Complexity: O(V + E)

Note: V is the number of vertices, E is the number of edges in graph G.