Data structure for solving Dynamic Connectivity problem.
Could be used to give quick answers to queries of the form "Is there a path between X and Y?" (i.e. "Do vertices X and Y belong to the same connected component?").
Implementation includes the following Quick-Find and Quick-Union algorithms:
| Algorithm | Union() time complexity (worst case) |
Find() time complexity (worst case) |
Memory complexity |
|---|---|---|---|
| Quick-Find | N |
1 |
N |
| Quick-Union | N |
N |
N |
| Weighted Quick-Union | log2(N) |
log2(N) |
2*N |
C++17 and CMake ≥ 3.18.
GoogleTest is obtained via FetchContent_MakeAvailable() and not required to be pre-installed.
CTest-based pipeline starting script cmake/Pipeline.cmake uses GCC, gcov, Python 3 for gcovr installation in venv and (optionally) system Valgrind installation.
| Problem of 1M sites and ... | ... 20K Union() / Find() pairs |
... 700K Union() / Find() pairs |
... 2M Union() / Find() pairs |
|---|---|---|---|
| Quick-Find | 21.1539 sec. |
— | — |
| Quick-Union | 0.012467 sec. |
35.1199 sec. |
— |
| Weighted Quick-Union | 0.016003 sec. |
0.468004 sec. |
1.20773 sec. |