Thread: 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.

-Thanks in advance!

You need a queue. Which is a class that allows you to shove things into an array at the end, and pop off and remove things from the front. Thus giving you First in First out system. I code in C++ , but Java is similiar enough you can read the code and make the proper syntax corretions. Note: I would symbolically change your graph to a NxN array of x,y points. So the above graph would go from 0,0 to 2,2. It would also be easier if you mirror imaged the number along the diagonal. For example
1----2----3
| ||
4----5----6
| | |
7----8----9
For any size N. 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.