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.

  • $\begingroup$ 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? $\endgroup$ – Henning Makholm Feb 22 at 9:41
  • $\begingroup$ OK, sorry. I am updating my question. $\endgroup$ – TobiR Feb 22 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.