Menu
Using disjoint-set data structure can easily get connected component of Graph. And, it just supports Incremental Connected Components.
However, in my case, removing edge is very common so that I am looking for an algorithm or new structure can maintain Connected Components fully dynamically(including adding and removing edge)
Thanks
440
As mentioned by others, running a BFS or DFS will allow you to efficiently count the number of connected components.
Perform depth-first search on the reversed graph. Start from the top vertex of the stack. Traverse through all of its child vertices. Once the already visited vertex is reached, one strongly connected component is formed.
First, mark all vertices as unvisited. Iterate over all vertices. If a vertex is not visited, perform DFS on that vertex and increment the count by 1. After iterating over all vertices, the value of count will be the number of connected components in the graph.
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (Holm, de Lichtenberg and Thorup 2001) gives an algorithm that allows an arbitrary sequence of edge insertions, deletions and connectivity queries, with updates (insertions and deletions) taking O(log(n)^2) amortised time, and queries taking O(log(n)/log(log(n))) time, with n being the number of vertices in the graph. These time bounds assume that the graph starts with no edges.
I only skimmed the first 2 of its 38 pages, but don't be (too) scared -- the paper describes a bunch of new algorithms on dynamic graphs (that is, graphs that can be efficiently modified over time) of which connectivity is the simplest.
130
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
