Finding a balanced spanning tree

402 Views Asked by At

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:

  1. Check if $G$ is connected. If not stop.
  2. Sort the edges in increasing order according to their edge weights.
  3. 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?