Results 1 to 2 of 2

Math Help - Finding all possible paths in an undirected graph (non infinite loops only)

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    2

    Question 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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2011
    Posts
    53
    Thanks
    1

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

    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.  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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. question about graphs / undirected tree
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 13th 2011, 12:58 PM
  2. Graph Theory - Trees and Paths
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 9th 2010, 11:14 PM
  3. Finding the number of paths...
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 18th 2010, 05:02 PM
  4. Cycles in an undirected graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2009, 12:30 AM
  5. Finding Price Paths from Difference Equations
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: August 1st 2009, 10:53 AM

Search Tags


/mathhelpforum @mathhelpforum