Spanning Tree

---

A spanning tree of a graph is a subgraph that connects all the vertices together without any cycles and with the minimum possible number of edges. Essentially, a spanning tree includes all the vertices of the graph, but only the necessary edges to ensure connectivity, without creating loops. Spanning trees are fundamental in various applications, including network design, circuit design, and algorithms such as Minimum Spanning Tree (MST), which plays a crucial role in optimizing networks.

---

What is a Spanning Tree?

In a graph $G=(V,E)$, where:

• $V$ is the set of vertices.
• $E$ is the set of edges.

A spanning tree is a subgraph $T$ of $G$, where:

• $T$ includes all vertices from the graph $G$.
• $T$ has no cycles.
• $T$ contains exactly $V-1$ edges (the minimum number of edges to connect all the vertices).

Properties of a Spanning Tree

1. Connectivity: A spanning tree connects all the vertices of the graph without any disconnected components.
2. Acyclicity: A spanning tree has no cycles, meaning it’s a tree.
3. Minimum Edges: A spanning tree has exactly $V-1$ edges, where $V$ is the number of vertices in the original graph.
4. Multiple Spanning Trees: A graph can have multiple spanning trees, especially if it has more than one edge between vertices.
5. Minimum Spanning Tree (MST): If the edges of the graph have weights, a spanning tree can be chosen to minimize the total weight. This is known as the Minimum Spanning Tree (MST).

---

Spanning Tree Applications

1. Network Design: Spanning trees are used in the design of networks (e.g., communication, electrical, or transportation networks), where we need to connect multiple nodes with the fewest number of connections while maintaining full connectivity.
2. Routing Algorithms: In computer networks and routing algorithms, spanning trees help in finding optimal paths for routing data efficiently.
3. Cluster Analysis: Spanning trees are used in clustering algorithms to create a hierarchy of data points.
4. Circuit Design: Spanning trees are applied in designing electrical circuits, ensuring that all components are connected with minimal wiring.

---

Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) is a spanning tree of a connected, undirected graph where the sum of the weights of the edges is minimized. If the graph has weighted edges, MST algorithms help to find the spanning tree with the least total weight.

Two well-known algorithms used to find the MST of a graph are Kruskal’s Algorithm and Prim’s Algorithm.

---

Algorithms for Constructing a Spanning Tree

1. Kruskal’s Algorithm

Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a graph. It works by considering edges in increasing order of their weight and adding them to the MST, provided they don’t form a cycle.

Steps of Kruskal’s Algorithm:

1. Sort all edges in the graph by their weights.
2. Initialize a forest, where each vertex is its own tree.
3. For each edge, check if it forms a cycle with the trees already in the forest. If it doesn’t, include the edge in the MST.
4. Repeat the process until there are $V-1$ edges in the MST.

Time Complexity: $O(E\log E)$, where $E$ is the number of edges.

Example:

Consider the following weighted graph:

     A
    / \
   1   3
  /     \
 B-------C
    2

• Vertices: $A,B,C$
• Edges: $(A,B,1),(A,C,3),(B,C,2)$

Step-by-step Kruskal’s Algorithm:

1. Sort edges by weight: $(A,B,1),(B,C,2),(A,C,3)$.
2. Add edge $(A,B)$ to the MST.
3. Add edge $(B,C)$ to the MST (does not form a cycle).
4. Skip edge $(A,C)$ because it would form a cycle.

MST: $(A,B,1),(B,C,2)$.

2. Prim’s Algorithm

Prim’s Algorithm is another greedy algorithm that grows the MST one edge at a time. It starts with an arbitrary vertex and repeatedly adds the smallest edge that connects a vertex in the MST to a vertex outside the MST.

Steps of Prim’s Algorithm:

1. Start with any vertex as the initial MST.
2. Find the smallest edge that connects a vertex in the MST to a vertex outside it.
3. Add the edge to the MST.
4. Repeat the process until all vertices are included in the MST.

Time Complexity: $O(E\log V)$, where $E$ is the number of edges and $V$ is the number of vertices.

Example:

Consider the same graph from above:

     A
    / \
   1   3
  /     \
 B-------C
    2

• Start with vertex $A$.
• The smallest edge connected to $A$ is $(A,B,1)$, so add it to the MST.
• Now, the smallest edge connected to the MST is $(B,C,2)$, so add it to the MST.

MST: $(A,B,1),(B,C,2)$.

---

Spanning Tree Example in Python (Kruskal’s Algorithm)

Below is an example of how to implement Kruskal’s algorithm to find the minimum spanning tree in Python:

# Kruskal’s Algorithm implementation for Minimum Spanning Tree

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

class Kruskal:
    def __init__(self, vertices, edges):
        self.V = vertices
        self.edges = edges

    def run(self):
        mst = []
        disjoint_set = DisjointSet(self.V)
        sorted_edges = sorted(self.edges, key=lambda x: x[2])

        for u, v, weight in sorted_edges:
            if disjoint_set.find(u) != disjoint_set.find(v):
                mst.append((u, v, weight))
                disjoint_set.union(u, v)
        return mst


# Example graph: (u, v, weight)
edges = [
    (0, 1, 1),
    (0, 2, 3),
    (1, 2, 2)
]

# Number of vertices in the graph
vertices = 3

kruskal = Kruskal(vertices, edges)
mst = kruskal.run()

print("Minimum Spanning Tree:")
for u, v, weight in mst:
    print(f"Edge: ({u}, {v}) with weight {weight}")

Output

Minimum Spanning Tree:
Edge: (0, 1) with weight 1
Edge: (1, 2) with weight 2

 

---

---