I am working on the following exercise:
Consider an undirected connected graph $G(V,E)$ with edge weights $w_e$ for $e \in E$. Devise an efficient algorithm that finds a balanced spanning tree, that is a spanning tree that minimizes $$max_{e \in E_T} w_e - min_{e \in E_T}.$$
My approach is the following:
- Check if $G$ is connected. If not stop.
- Sort the edges in increasing order according to their edge weights.
- Traverse the edges, starting from the smallest and add it to $T$ if it contains an unvisited vertex. Mark the newely visited vertices.
Is this correct?