Spanning Tree in Data Structure with Examples: A Complete Guide for Beginners

Understanding Spanning Tree in Data Structure is crucial if you're diving into graph theory, competitive programming, system design, or network optimization.

In this blog, we’ll cover:

• 1. What a Spanning Tree is
• 2. Key properties and types
• 3. Real-world applications
• 4. Code examples (including Prim’s and Kruskal’s algorithms)
• 5. And how you can master it with Uncodemy
   

What Is a Spanning Tree?

A spanning tree is a subgraph of a connected undirected graph that:

• 1. Includes all the vertices of the original graph
• 2. Is connected
• 3. Has no cycles
•  

In short, it "spans" all vertices with the minimum number of edges to keep them connected.

Example:

Consider this connected graph:

css

CopyEdit

    A

   / \

  B---C

   \ /

    D

A possible spanning tree:

css

CopyEdit

    A

   / \

  B---C

   \ /

    D

Here:

• All 4 vertices are connected
• No cycles
• Only 3 edges for 4 vertices
   

✅ That’s a spanning tree!

Key Properties of a Spanning Tree

1. If a graph has V vertices, a spanning tree will always have V - 1 edges.

2. No cycles are allowed (makes it a tree, not a graph).

3. Multiple spanning trees are possible for a single graph.

4. Minimum Spanning Tree (MST) is a special type with minimum total edge weight.

Why Is Spanning Tree Important?

• 1. Reduces complexity in networks
   
• 2. Removes redundancy in connections
   
• 3. Forms the base of important algorithms like Prim's, Kruskal's, and Borůvka’s
   
• Used in:
   
  • 1. Computer networking (Spanning Tree Protocol)
     
  • 2. Electrical grid design
     
  • 3. Road/railway optimization
     
  • 4. Clustering in Machine Learning

Types of Spanning Trees

1. General Spanning Tree

Any tree that connects all vertices without forming cycles.

2. Minimum Spanning Tree (MST)

A spanning tree with the least total weight. Among all possible trees, MST is optimal for cost-based applications.

Number of Spanning Trees

For a complete graph with n vertices:

• Total spanning trees = n^(n-2)
   
• (Using Cayley’s Theorem)
   

Example:

• For 3 vertices: 3^(3-2) = 3
   
• For 4 vertices: 4^(4-2) = 16

Finding Spanning Trees: Algorithms

✅ 1. Kruskal’s Algorithm

• Works by sorting all edges by weight
   
• Adds lowest-weight edges without forming a cycle
   
• Uses Union-Find data structure

C Code Snippet:

c

CopyEdit

// Pseudo-code structure for clarity

Kruskal(graph):

  sort all edges by weight

  for each edge (u, v):

    if u and v are not connected:

      add edge to tree

✅ 2. Prim’s Algorithm

• Starts with one vertex
• Adds the lowest-weight edge that connects to a new vertex
• Greedy approach

C Code Snippet:

c

CopyEdit

// Pseudo-code structure for clarity

Prim(graph):

  start with vertex 0

  for each adjacent edge:

    pick the minimum weight edge that connects to unvisited vertex

Example: Minimum Spanning Tree

Let’s use this graph:

less

CopyEdit

     A

   / | \

  B--C--D

With edge weights:

• AB = 2
   
• AC = 3
   
• AD = 6
   
• BC = 1
   
• CD = 5
   

Using Kruskal’s:

BC (1)

AB (2)

AC (3) → Skip (would form cycle)

CD (5)

Final MST edges: BC, AB, CD
 Total weight = 1 + 2 + 5 = 8

Implementation in C: Prim’s Algorithm

c

CopyEdit

#include <stdio.h>

#include <limits.h>

#define V 5

int minKey(int key[], int mstSet[]) {

    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)

        if (mstSet[v] == 0 && key[v] < min)

            min = key[v], min_index = v;

    return min_index;

}

void printMST(int parent[], int graph[V][V]) {

    printf("Edge \tWeight\n");

    for (int i = 1; i < V; i++)

        printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);

}

void primMST(int graph[V][V]) {

    int parent[V]; 

    int key[V];    

    int mstSet[V];

    for (int i = 0; i < V; i++)

        key[i] = INT_MAX, mstSet[i] = 0;

    key[0] = 0;     

    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {

        int u = minKey(key, mstSet);

        mstSet[u] = 1;

        for (int v = 0; v < V; v++)

            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])

                parent[v] = u, key[v] = graph[u][v];

    }

    printMST(parent, graph);

}

int main() {

    int graph[V][V] = {

        {0, 2, 0, 6, 0},

        {2, 0, 3, 8, 5},

        {0, 3, 0, 0, 7},

        {6, 8, 0, 0, 9},

        {0, 5, 7, 9, 0}

    };

    primMST(graph);

    return 0;

}

Output:

nginx

CopyEdit

Edge    Weight

0 - 1   2

1 - 2   3

1 - 4   5

0 - 3   6

Real-World Applications of Spanning Tree

Learn Graph Algorithms with Uncodemy

If you’re serious about mastering data structures and algorithms, it's time to enroll in Uncodemy’s Data Structure and Algorithm Course in Noida.

Why Uncodemy?

✅ Learn from top industry experts
✅ Hands-on implementation of graph algorithms
✅ Real-world problem-solving skills
✅ Ideal for college students and job seekers
✅ Interview preparation + certification

From graphs and trees to recursion and sorting, Uncodemy equips you to crack coding interviews and build efficient software.

Recap: What You Learned

• 1. A spanning tree is a subgraph that includes all vertices without cycles
   
• 2. A Minimum Spanning Tree (MST) minimizes the total edge cost
   
• 3. Prim’s and Kruskal’s are two popular MST algorithms
   
• 4. Applications include network routing, clustering, and system design
   
• 5. Coding examples in C help understand real implementation
•  

Final Thoughts

Understanding the spanning tree in data structure isn’t just about passing exams—it’s about solving real problems in computer science and the world. Whether you're optimizing a network or building a road map, spanning trees offer an efficient and elegant solution.

So take this knowledge, try out the algorithms, and practice coding them yourself. And if you're ready to take your skills to the next level, Uncodemy is here to support your learning journey.