Suppose you have a graph G, and you want to support the following operations:

  • addNode(Node n)
  • addEdge(Node n1, Node n2)
  • deleteNode(Node n)

Now I want to track after every operation what the connected components of my graph are. If I only had to support addNode and addEdge, I would use a Union-Find data structure to maintain this information after every operation.

However, how does one support deletion operations? My current thought is that I must run several BFS operations on my graph to recompute all the connected components of the graph again.

Is there a more efficient way to support the delete operation?

  • $\begingroup$ Have you looked at dynamic connectivity, i.e., incremental connected components? $\endgroup$ – Juho May 20 at 17:26
  • $\begingroup$ Ahh thanks, this was the resource I was looking for. Looks like the solution to the problem is fairly difficult... $\endgroup$ – CowZow May 20 at 17:48

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.