Boruvka MST algorithm using doubly linked lists

Question

I'm reading Sedgewick & Wayne's Algorithms book, and one of the questions in one of the chapters is the following:

Develop an implementation of Boruvka's algorithm that uses doubly-linked circular lists to represent MST subtrees so that subtrees can be merged and renamed in time bounded by E during each stage (and the union-find data type is therefore not needed).

I'm aware of the standard version of Boruvka's algorithm that uses a union-find data structure to do the merges and check subtree identifiers (there is also an implementation on the book's official website )

But I'm not being able to figure out how to improve the performance of the algorithm by replacing the union-find data structure for subtrees represented by doubly-linked circular lists.

Any ideas? Thanks!

Answer 1

I came across your question in pursuit of the same answer. Anyway this comment gives a hint, I would say, why a detailed algorithm is not there or easily searchable:

"It is possible to remove the lg*E factor to lower the theoretical bound on the running time of Boruvka’s algorithm to be proportional to E lg V, by representing MST subtrees with doubly-linked lists instead of using the union and find operations. However, this improvement is sufficiently more complicated to implement and the potential performance improvement sufficiently marginal that it is not likely to be worth considering for use in practice (see Exercises 20.66 and 20.67)."

(from: http://apprize.info/c/algorithms_2/36.html)