You should stick with HashMap<Key,Value>. It allows for .contains() queries in O(1) time as opposed to ArrayList, which is O(n). At the very least, use HashSet<Key>, that also allows for O(1) time.
If I were you, I'd look into A* search. You want the shortest distance, it's optimal. That all said, it sounds like what you need is something similar to the way I'm doing multiblocks. This may prove somewhat useful to you, particularly the checkNeighbors() method, which is called whenever a block is placed. It basically checks each neighbor to see if they are an instance of the network type, and if they are, it joins the network; otherwise, it forms a new network. Ought to have a lot of cross-over application with your aims.
I'm gonna warn you right now, the code for this is still fairly buggy on edge-cases. When a network is split in half and the blocks on one half have to re-resolve the master node, that just gets ugly. You can make yours simpler by implementing a true master/slave architecture in your blocks, rather than the virtual master/slave architecture I decided to implement for the challenge of it.