Introduction

Yes, minimum-depth spanning trees do exist, but the right algorithm depends on what "minimum depth" means. In an unweighted graph, if the root is fixed, a breadth-first search tree already gives a spanning tree of minimum depth from that root. If the root is not fixed, the problem becomes: find a graph center, then build a BFS tree from it.

Define the Problem Carefully

A spanning tree contains all vertices of a connected graph and no cycles. The depth of a rooted spanning tree is the maximum number of edges from the root to any vertex in the tree.

That means there are two common versions of the problem:

• fixed-root version: given a root r, find a spanning tree with minimum depth from r
• free-root version: choose both the root and the spanning tree to minimize the depth

These are not the same problem. Once you separate them, the algorithmic picture gets much cleaner.

Fixed Root: BFS Is Optimal

Suppose the root r is fixed. Then a BFS tree from r is a minimum-depth spanning tree rooted at r.

Why? BFS visits vertices in nondecreasing order of shortest-path distance from the root. So for every vertex v, the depth of v in the BFS tree equals the shortest path distance from r to v in the graph. No other spanning tree rooted at r can place v at a smaller depth than its graph distance from r.

Therefore, the depth of the BFS tree is exactly the eccentricity of r, meaning the maximum shortest-path distance from r to any vertex. That is the best possible for that root.

Here is a small Python example that builds a BFS tree and reports its depth:

1from collections import deque
2
3
4def bfs_tree(graph, root):
5    parent = {root: None}
6    depth = {root: 0}
7    q = deque([root])
8
9    while q:
10        node = q.popleft()
11        for neighbor in graph[node]:
12            if neighbor not in parent:
13                parent[neighbor] = node
14                depth[neighbor] = depth[node] + 1
15                q.append(neighbor)
16
17    if len(parent) != len(graph):
18        raise ValueError("graph must be connected")
19
20    return parent, max(depth.values())
21
22
23graph = {
24    'A': ['B', 'C'],
25    'B': ['A', 'D'],
26    'C': ['A', 'E'],
27    'D': ['B', 'E'],
28    'E': ['C', 'D']
29}
30
31parents, tree_depth = bfs_tree(graph, 'A')
32print(parents)
33print(tree_depth)

For the fixed-root case, this is the standard answer. There is no need for something more exotic.

Free Root: Find a Graph Center

If you may choose the root, then you want the smallest possible eccentricity over all vertices. That value is called the graph radius, and any vertex achieving it is called a center.

Once you find a center, run BFS from it. The resulting BFS tree has minimum possible depth among all rooted spanning trees of the graph.

The logic is straightforward:

1. every spanning tree path is also a graph path candidate, so depth cannot beat shortest-path distances
2. the best possible root is one with smallest maximum distance to all other vertices
3. BFS from such a root achieves that lower bound exactly

A direct implementation is:

1from collections import deque
2
3
4def eccentricity(graph, start):
5    dist = {start: 0}
6    q = deque([start])
7
8    while q:
9        node = q.popleft()
10        for neighbor in graph[node]:
11            if neighbor not in dist:
12                dist[neighbor] = dist[node] + 1
13                q.append(neighbor)
14
15    if len(dist) != len(graph):
16        raise ValueError("graph must be connected")
17
18    return max(dist.values())
19
20
21def graph_center(graph):
22    best_node = None
23    best_ecc = None
24    for node in graph:
25        ecc = eccentricity(graph, node)
26        if best_ecc is None or ecc < best_ecc:
27            best_node = node
28            best_ecc = ecc
29    return best_node, best_ecc
30
31
32center, radius = graph_center(graph)
33print(center, radius)

This brute-force approach runs BFS from every vertex. It is fine for small to medium graphs and makes the idea explicit.

Weighted Graphs and Other Variants

If edges have weights and depth means number of tree levels, BFS no longer answers every question automatically. If the objective becomes minimizing the maximum weighted distance from the root, then the shortest-path metric changes, and Dijkstra-style computations matter.

If the graph is directed, or if you want additional constraints such as bounded degree or minimum total weight at the same time, the problem can become harder. Some variants are optimization problems that are no longer solved by one plain BFS.

So the correct statement is not "minimum-depth spanning tree is NP-hard" in general. For the ordinary unweighted connected graph version, it is easy.

Common Pitfalls

A common mistake is confusing minimum-depth spanning trees with minimum spanning trees. MST algorithms minimize total edge weight, not tree depth.

Another mistake is forgetting to specify the root. The answer changes depending on whether the root is fixed or free.

People also sometimes assume a DFS tree might be just as good. It can be much deeper than necessary because DFS does not preserve shortest-path layers.

Finally, if the graph is disconnected, no spanning tree exists. You would then need a spanning forest instead.

Summary

• For a fixed root in an unweighted connected graph, a BFS tree is a minimum-depth spanning tree
• If the root is not fixed, choose a graph center and run BFS from it
• The optimal minimum depth equals the graph radius
• Minimum spanning tree algorithms solve a different objective
• Weighted, directed, or constrained variants can require different algorithms
• Always state whether the root is fixed before discussing complexity or optimality