# Union Find Algorithm

article

## Is there a path between A and B?

Tags: Grid Graph Reachability Union Find Coursera  Java 2015

## 1Introduction

I encounterd this useful algorithm during a course at coursera.org. It has many applications, and I hope this article is useful to you.

Consider a pathfinding problem on a undirected grid graph. We want to get from (A) to (B). It would be nice to check if a path exists at all, before launching any time-consuming attempts.

We don't need the path itself, just an answer to the question: Is B reachable from A?

There is a simple, fast and beautiful algorithm with great scalability that answers this question, called: Union-Find

## 2Resources

This algorithm is part of a course given Kevin Wayne & Robert Sedgewick from Princeton University.

Union-Find Java example code:

## 3Usage example

To investigate two points, (A) and (B), on a grid graph.

1. Construct a "grid" of nodes
2. Connect each node with it's neighbors, if the path is not blocked between them
3. Query reachability

The Union-Find code example is able to tell wether 2 nodes are connected. Either directly or through neighbours.

Write a class that instantiates a Union-Finder. Make room for N nodes, where

`N = length x width`
.

1) Visualise the node ordering like follows: 2) Connect nodes using the union method, use ID's considering the ordering above. To make a vertical connection between node-3 and node-10:

```EXAMPLE
finderInstance.union(3, 10);```

3) Query reachabillity between (A) and (B) through the command

`finderInstance.connected(idA, idB);`

## 4Further reading and thoughts

The above algorithm is more specifically called:"Weighted quick-union with path compression". The amortized cost [?] per operation for this algorithm is known to be bounded by a function known as the inverse Ackermann function and is less than 5 for any conceivable practical values of N.

#### Alternatives

An alternative solution is given in the paper "Optimal decremental connectivity in planar graphs", by Jakub Łącki, Piotr Sankowski. Which is said to run in constant time per query/operation. PDF download is at the right. Anyone tried this? Please let us know in the comments below.

#### Application in Vector Racer

The above can be applied to VectorRacer as well. For instance: to check if a track is valid before computing AI paths.

Consider the car accelerating and then immediatly braking each time. Moving 1 position and then comming to a full stop.
This stop-and-go driving removes the momentum from the equation and simplifies to the above grid graph problem.

You wouldn't be fast riding like this, but for that we have different algorithms :)