Is g reachable from a? — NO
Is there a path between i and h? — YES
However, to make things more interesting, our graph is not static
and we can link two nodes.
This problem can be formulated a little more abstractly: given a collection of disjoint sets, we would like to support the following two operations:
union(A,B)– replaces sets A and B with their union
find(x)– find set X where x belongs.
In our network application, the nodes reachable from each other form disjoint sets (called connected components). By linking two nodes from two different components, we get one big component – their union. Nodes x and y are connected by a path if and only if they belong to the same component, i.e., if
Link f and j: union C and E
Link b and g: union A and D
Link a and h; link a and d
Gilbert et al. (1994) An efficient algorithm to compute row and column counts for sparse Cholesky factorization. SIAM Journal on Matrix Analysis and Applications, 15:1075.
Gabow, H. and Tarjan, R. (1985). A linear-time algorithm for a special case of disjoint set union. Journal of computer and system sciences, 30(2):209–221.