# Is there any chance to reconstruct a BFS tree after removing one of its edges less expensively than repeat the complete spanning tree search?

I just wanted to ask whether there is any cheap way to reconstruct a BFS tree after deletion of one of its edges. It would be useful for me when I should leave out several edges from the BFS tree. While building a spanning tree, I use the edge-adjacency list ($$i.e.$$, collection of edges incident to a given node) for each node. The BFS tree is stored by saving the ancestors of the nodes in the tree. After removal of an edge, I would like to reconstruct the ancestors of the nodes such that they represent a BFS tree of the remaining graph.

• Please explain what "reconstruct a BFS tree after deletion of one of its edges" means to you. Which information do you have available as input? What do you want to end up with? – Henning Makholm Feb 22 at 9:41
• OK, sorry. I am updating my question. – TobiR Feb 22 at 9:42