CODEWITHSUNDEEP
algorithmgraph
Guangyi Tao
Guangyi Tao

Reputation: 11

Best way to detect if a path exists between two nodes a graph?

The description of the question is the following.

A program would read a file by lines to build up a graph. Each line in the file would be one of theses three kinds of operations:

  1. add x y, which means adding an edge between node x and y,so that a graph would be formed. This graph is a undirected graph.
  2. remove x y, which means removing an edge between node x and y, if it's not valid(x or y does not appear to exist in graph or not edges exists between x and y), then do nothing.
  3. is linked x y, which should return if x and y can be connected through all the edges in the graph. The time complexity of this operation should be constant time.

Here is an example:

   add 1 2  
   add 2 3
   is linked 1 3(should be true ,cause there is a path 1-> 2, 2->3)
   add 3 4
   remove 2 3
   is linked 1 4(should be false)

Upvotes: 0

Views: 287

Answers (1)

Bonje Fir
Bonje Fir

Reputation: 840

You can use union-find data structure to do that in amortized time of near linear. For its structure and implementation details you can google the union by rank with path compression. You can find many academic notes about that with pictorial tutorials and precise time/space-complexity analysis. This link and this one can help.

But two notes here:

Its complexity is amortized. See here if you want to compare it with worst-case analysis.

What means near linear? The amortized analysis of the algorithm is equal to inverse Ackermann function noted by α ( n ).

where α ( n ) {\displaystyle \alpha (n)} \alpha (n) is the inverse Ackermann function. This function has a value α ( n ) < 5 {\displaystyle \alpha (n)<5} {\displaystyle \alpha (n)<5} for any value of n that can be written in this physical universe, so the disjoint-set operations take place in essentially constant time

Upvotes: 1

Related Questions