# Thread: Finding all possible paths in an undirected graph (non infinite loops only)

1. ## Finding all possible paths in an undirected graph (non infinite loops only)

Hi,
i've managed to use BreadthFirstSearch to traverse all possible nodes
but I only come up with one path - the one first discovered.
Is there a way to record all the different possible paths.

Example:
Say we have 9 nodes.

1----4----7
| | |
2----5----8
| | |
3----6----9

note: the "|" represents bidirectional connections for 1 and 2. The same for the rest.
I just can't seem to align them properly

Where all nodes connected with a line bidirectionally.
Like 1 is connected to 4 and 2, so 2 and 4 are connected to 1.

How can I save all possible paths from 2 to 1.
These would be:
2-1,
2-5-4-1,
2-3-6-5-4-1,
2-3-6-9-8-5-4-1,
2-3-6-9-8-7-4-1,
2-5-6-9-8-7-4-1,
2-5-8-7-4-1,

I think I've covered it all.
Can anyone guide me with pseudocode? Or even Java can work.

For any size N. $Location(x,y)=N*(y)+x+1$ This arrangement is the more normal way of reading arrays in code. But if your original way of drawing is necessary flip the x,y in the equation above.. us y co-ords to go left/right and x to go up/down in the code. The code might be a little longish for the forums. So if you want just PM and i could email you some code I have already.