maintaining a balanced spanning tree of a growing undirected graph

Question

I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph.

I have an undirected graph that starts as a single node, the "root".

At each step, I add to the graph either a new node and an edge connecting it to the graph, or just a new edge, connecting two old nodes. As I grow the graph, I maintain a spanning tree. Most of the time, this means that when I add a new node and edge, I set the new node to be the child of the old node that it connects to.

I have no control over the order in which the new nodes are added, so the above tree-building algorithm can obviously lead to imbalanced spanning trees.

Does anybody know of online heuristics that will keep the spanning tree "relatively balanced", while minimizing the amount of work done in re-treeing? I have full control over the tree structure. What I don't control is the graph connectivity, or the order in which new nodes are added.

Note that the standard Google responses to terms like "balanced" "spanning" and "tree" seem to be binary trees and B-trees, neither of which apply. My graph nodes can have any number of neighbors, so the tree nodes can have any number of children, not 2 like binary trees. B-trees maintain balance by changing their adjacency lists, and I cannot change the graph connectivity.

Answer 1

Every time you add a new vertex with an edge, you don't have options. Every time you add a new edge, if the current distance to the root is bigger than the distance through the new edge, you remove the old edge in the old shortest path and add the new one. Otherwise, you just keep your tree unchanged. I think this way you get something very similar to a BFS tree in the sense that the levels of the tree will contain the same vertices and the distance from a vertex to the root will be the same as the distance in the BFS tree (and in the graph), but I don't know if that's enough to satisfy your "ideal balanced spanning tree" condition.

Answer 2

I ended up doing the following:

Vinicius Santos' answer is the first part of it. As he says, at any frame I either add a new node and a parent-child edge connecting to it, or just add a cross-edge between two existing nodes. Parent-child edges offer no opportunities for changing the tree structure, only cross-edges do. Consider adding a cross-edge E between nodes A and B, where B has the greater tree depth. If (A.depth + 1) < B.depth, then we can lessen B.depth by making it a child of A.

Having lessened the depth of B, we now must check B's neighbors, to see if they may lessen their depth by becoming children of B. We therefore perform a breadth-first traversal from B, which traverses an edge from X to Y if X.depth+1 < Y.depth, and sets Y to be a child of X.