What Is Spanning Tree: Definition, Example, and Uses

A spanning tree is a subset of a connected graph that includes all the vertices with the minimum number of edges needed to keep the graph connected, without any cycles. It connects every point in the graph with the least possible links, forming a tree structure.

How It Works

Imagine you have a network of cities connected by roads, and you want to connect all cities with the fewest roads possible so that you can travel between any two cities without any loops or extra paths. A spanning tree is like choosing just enough roads to keep all cities connected without any circular routes.

In graph terms, a spanning tree takes all the points (called vertices) and connects them with edges so that there is exactly one path between any two points. This means no cycles or loops exist, and the graph remains connected. The number of edges in a spanning tree is always one less than the number of vertices.

Example

This example shows how to find a spanning tree from a simple graph using Python. It uses a basic approach to pick edges without creating cycles.

python

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v):
        self.graph.append([u, v])

    def find_parent(self, parent, i):
        if parent[i] == i:
            return i
        return self.find_parent(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find_parent(parent, x)
        yroot = self.find_parent(parent, y)

        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def spanning_tree(self):
        result = []
        i = 0
        e = 0

        self.graph = sorted(self.graph, key=lambda item: item[0])

        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1 and i < len(self.graph):
            u, v = self.graph[i]
            i += 1
            x = self.find_parent(parent, u)
            y = self.find_parent(parent, v)

            if x != y:
                e += 1
                result.append([u, v])
                self.union(parent, rank, x, y)

        return result

# Create a graph with 4 vertices
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

spanning_tree_edges = g.spanning_tree()
print("Edges in the spanning tree:")
for u, v in spanning_tree_edges:
    print(f"{u} - {v}")

Output

Edges in the spanning tree:
0 - 1
0 - 2
1 - 3

When to Use

Spanning trees are useful when you need to connect all points in a network efficiently without any loops. For example, in designing computer networks, a spanning tree helps avoid data loops that can cause network failures.

They are also used in electrical grid design, road planning, and clustering data points in machine learning. Whenever you want to ensure connectivity with minimum connections and no cycles, spanning trees are the right choice.

Key Points

• A spanning tree connects all vertices with the minimum number of edges.
• It contains no cycles, so there is exactly one path between any two vertices.
• The number of edges in a spanning tree is always one less than the number of vertices.
• Spanning trees are essential in network design to avoid loops and ensure efficient connectivity.

Key Takeaways

A spanning tree connects all points in a graph with the fewest edges and no cycles.

It ensures there is exactly one path between any two vertices.

Spanning trees are crucial for efficient and loop-free network designs.

The number of edges in a spanning tree is always vertices count minus one.