# How to Track Connected Components in a Graph when Deleting Nodes

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?

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