i still suggest you leave the roots til after sorting out all edges not included in the tree, they will be growing in a quadratic manner, the tree linearily (1000 nodes gives 999 times sqrt after but 500000 before, and expensive operations like sqrt will become really nasty in these quantities)

an array could be nasty if you resize it when its large, a middle thing would be to use a tree, but it consumes more memory, but in this case its nothing, trees can keep themselves sorted, while you add items to them. alternatively you could use a heap, especially if you drop chunks of items on them, or a hashtable, but they are arrays as well. lists would definitely be the worst option still.