Breadth first search algorithm in Java (with visited paths)

Basically, there are two widely used algorithms for traversing graphs – BSF (Breadth First Search) and DSF (Depth First Search).

BSF – goes level by level in graph. It visits first all parent’s children, then all children’s children and so on. For implementing BSF, most important keyword is – queue. First you take all parent’s children and examine them one by one. If you don’t find what you are looking for on that level, you take all children’s children (grandchildren) and put them at the end of the queue. Then you take a next element from the queue and continue. With BSF you are sure you will find “closest” nodes. “Closest” means with shortest vertices.

DSF – goes in depth first. Reads all children, if not found then takes one child and reads his children, and so on. For implementing DSF, most important keyword is – stack. You put one by one node on stack, and recursively pop them up.

There are many BSF/DSF implementations in Java available on net, but somehow none of them fitted my needs. I needed not only to find *all* possible connections between two nodes, but also to remember all nodes in between that I have visited. Actually, I wanted to know all connections between two nodes Nx and Ny.