It sounds like you are looking for the iterator pattern. This should get you going in the right direction...
Frank V
2009-06-15 21:34:37
A:
+1
A:
Do either a BFS or a DFS, and keep track of the path along with the node. When the node has no more children, dump the path. Note that you have a graph/forest instead of a tree, but the algorithm I outlined will work just the same.
To start you off using a BFS:
Step 1. [n1]
Step 2. [n2(n1), n3(n1)]
Step 3. [n3(n1), n4(n1,n2)]
Step 4. [n4(n1, n2), n4(n1, n3)]
Step 5. [n4(n1, n3), n5(n1, n2, n4), n6(n1, n2, n4), n10(n1, n2, n4)]
Step 6. [n5(n1, n2, n4), n6(n1, n2, n4), n10(n1, n2, n4), n5(n1, n3, n4), n6(n1, n3, n4), n10(n1, n3, n4)]
...
and so on. In the end you will have your paths. which will get printed out. You can implement this algorithm without requiring recursion. Just loop till the array is empty. Makes sense?
Ryan Oberoi
2009-06-15 21:35:21
Thanx, the DFS is exactly what i needed. i am implementing my own version of it in c#, now. will post in a few days when complete so others can use it.
see_sharp_guy
2009-06-15 21:56:29
Keep in mind that this only works assuming your graph is acyclical, and there is exactly one "foot" node which has no out bound edges. These seem like reasonable assumptions, but I'd state them explicitly before turning in the assignment if it were me. Without both of these assumptions, the problem and solution are more complex.
Mike Deck
2009-06-15 22:30:22
Solution above works for multiple foot nodes and for various depths of the tree, as long as he prints and removes nodes when "list" on the nodes is empty. Will not terminate if the graph has a cycle.
Ryan Oberoi
2009-06-15 23:21:22
+1
A:
That's a graph, not a tree. http://en.wikipedia.org/wiki/Tree_structure
So... my pointer would be, you're looking for a solution in graph theory. If you get stuck, a bit of google-fu around that term and your problem should yield algorithms to implement.
Brabster
2009-06-15 21:36:13
In a directed graph, the edges point from somewhere to somewhere. Not the case in your graph. Your graph is a undirected graph.
Brabster
2009-06-15 21:54:00
A:
You may find this wikipedia article helpful - it discusses the various kinds of tree traversal you can do. However, most likely what you want is a recursive descent, prefix traversal. Furthermore, the structure you describe is not a traditional tree - in that it has cross-shared nodes - it is probably a graph. There are some graph traversal algorithms as well. Just keep in mind, that if the graph has cycles, you will need to provide some kind of cycle detection to handle terminating the traversal.
LBushkin
2009-06-15 21:38:03