Graphs and Network Algorithms · Graph Algorithms

Spanning Tree

A spanning tree connects all vertices without cycles; a minimum spanning tree does so with minimum total edge weight.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

We use network-building examples so spanning trees feel practical.

Guided Lesson Notes

Understanding Spanning Tree

A spanning tree starts with a connected, undirected graph and keeps just enough edges to connect every vertex. If the original graph has V vertices, any spanning tree for that graph has exactly V - 1 edges.

The tree part matters: once a chosen edge creates a cycle, the edge is extra for connectivity. Removing one edge from that cycle still leaves the vertices connected, so a spanning tree should stay cycle-free.

A minimum spanning tree adds weights to the story. When edges represent costs such as cable length, road cost, or network latency, the minimum spanning tree is the spanning tree with the smallest total edge weight.

Visual Model

Graph, spanning tree, and MST

Highlighted MST

The blue edges connect all five vertices, create no cycle, and have total cost 13.

Rule of Thumb

For V vertices, a spanning tree uses V - 1 edges. Here, 5 vertices means 4 chosen edges.

Core Test

Connected plus no cycle is the spanning-tree test. Minimum total weight is the MST test.

Key Ideas

Cycle-free connectivity
Weighted edge choice
Network design motivation

Practice Prompts

Find a spanning tree by removing cycle edges.
Compare two spanning trees by total weight.

Vocabulary

Terms students should be able to say clearly

Vertex

A point in the graph, such as a city, computer, room, or course.

Edge

A connection between two vertices. In MST problems, edges usually have weights.

Connected graph

A graph where every vertex can be reached from every other vertex.

Cycle

A path that returns to a vertex already visited. Spanning trees avoid cycles.

Spanning tree

A connected, cycle-free subset of edges that includes every vertex.

Minimum spanning tree

A spanning tree whose edge weights have the smallest possible total.

Worked Example

Worked example: choose the lowest-cost network

Imagine five rooms, A through E, that need network cable. Each possible cable has a cost. The goal is not to use every cable; the goal is to connect every room with the smallest reliable set of cables.

1List the vertices: A, B, C, D, and E. A spanning tree must include all five rooms.
2Because there are five vertices, a valid spanning tree must choose exactly four edges.
3Choose edges that connect new vertices without making a cycle. If an edge closes a loop, skip it for the tree.
4For a minimum spanning tree, prefer low-cost edges, but only when they do not create a cycle.
5Add the chosen edge weights. If every room is connected and the total cannot be improved, you have an MST.

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Validate a spanning tree	O(V + E)	Check that all vertices are reached and no extra cycle-forming edges are included.
Kruskal MST	O(E log E)	Sort edges by weight, then use union-find to avoid cycles.
Prim MST	O(E log V)	Use a priority queue to choose the cheapest edge from the growing tree to a new vertex.

Common Mistakes

What to watch while practicing

Including every low-cost edge without checking whether it creates a cycle.
Forgetting that a spanning tree with V vertices must have exactly V - 1 edges.
Solving an MST problem on a disconnected graph without first noticing that no spanning tree exists.
Confusing shortest path with minimum spanning tree: shortest path connects two endpoints, while MST connects every vertex.

Interview-Style Coding Problem

Spanning Tree interview problem: Minimum Cost to Connect All Cities

Interview medium

Problem

Given possible undirected connections between cities, find the minimum total cost to connect every city.

Input

The first line contains n and m. The next m lines contain u v cost using 1-based city labels.

Output

Print the minimum cost, or -1 if the graph cannot be fully connected.

Sample Input

Sample Output

Why the sample works

The minimum spanning tree uses costs 1, 2, and 3 for a total of 6.

Approach

1Sort all connections by cost.
2Use union-find to avoid cycles.
3Take an edge only if it connects two different components.
4The graph is connected only if exactly n - 1 edges are chosen.

O(m log m) time and O(n) extra space.

Java Solution

import java.util.*;

public class Main {
  static class DSU {
    int[] parent;
    int[] rank;

    DSU(int n) {
      parent = new int[n + 1];
      rank = new int[n + 1];
      for (int i = 1; i <= n; i++) parent[i] = i;
    }

    int find(int x) {
      if (parent[x] != x) parent[x] = find(parent[x]);
      return parent[x];
    }

    boolean union(int a, int b) {
      int ra = find(a);
      int rb = find(b);
      if (ra == rb) return false;
      if (rank[ra] < rank[rb]) {
        parent[ra] = rb;
      } else if (rank[ra] > rank[rb]) {
        parent[rb] = ra;
      } else {
        parent[rb] = ra;
        rank[ra]++;
      }
      return true;
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[][] edges = new int[m][3];
    for (int i = 0; i < m; i++) {
      edges[i][0] = sc.nextInt();
      edges[i][1] = sc.nextInt();
      edges[i][2] = sc.nextInt();
    }

    Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
    DSU dsu = new DSU(n);
    int used = 0;
    long cost = 0;

    for (int[] edge : edges) {
      if (dsu.union(edge[0], edge[1])) {
        used++;
        cost += edge[2];
      }
    }

    System.out.println(used == n - 1 ? cost : -1);
  }
}

Python Solution

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
edges.sort(key=lambda x: x[2])

parent = list(range(n + 1))
rank = [0] * (n + 1)

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    elif rank[ra] > rank[rb]:
        parent[rb] = ra
    else:
        parent[rb] = ra
        rank[ra] += 1
    return True

used = 0
cost = 0
for u, v, w in edges:
    if union(u, v):
        used += 1
        cost += w

print(cost if used == n - 1 else -1)

Practice Challenge

Make the idea your own

Draw a connected weighted graph with six vertices. Build one spanning tree that is not minimum, then use Kruskal or Prim to find a better one. Explain every edge you accept or reject.

Tutoring Connection

Turn the topic into usable problem-solving skill

Students can use this page before a lesson, after a difficult homework assignment, or while preparing for AP Computer Science A extensions, Advanced Topics in CS, USACO growth, or a college data structures course.

Schedule Free Consultation Text Us Open Online Compiler