<p>Looking for a good approach to keep track of a Breadth-First traversal between two nodes, without knowing anything about the graph. Versus Depth-First (where you can throw away the path if it doesn't pan out) you may have quite a few "open" possibilities during the traversal.</p>

[{'answer_id': 57509, 'author': 'Joseph Bui', 'author_id': 3275, 'author_profile': 'https://Stackoverflow.com/users/3275', 'pm_score': 2, 'selected': False, 'text': "<p>The naive approach is to build a tree with the source node as the root and all its connections as its children. Depending on the amount of space you have, you might need to eliminate cycles as you go. You can do that with a bitmap where each bit corresponds to a distinct node in the graph. When you reach the target node, you can follow the parent links back to the root and that is your path. Since you are going breadth first, you are assured that it is a shortest path even if you don't eliminate cycles.</p>\n"}, {'answer_id': 57836, 'author': 'mweerden', 'author_id': 4285, 'author_profile': 'https://Stackoverflow.com/users/4285', 'pm_score': 1, 'selected': False, 'text': '<p>For a breadth-first search you need to store at least two things. One is the set of already visited nodes and the other is the set of nodes that are directly reachable from the visited nodes but are not visited themselves. Then you keep moving states from the latter set to the former, adding newly reachable states to the latter. If you need the have a path from the root to some node(s), then you will also need to store a parent node for each node (except the root) in the aforementioned sets.</p>\n\n<p>Usually the union of the set of visited nodes and the set of not-visited child nodes (i.e. the set of seen nodes) is stored in a hash table. This is to be able to quickly determine whether or not a "new" state has been seen before and ignore it if this is the case. If you have really big number of states you might indeed need a bit array (as mentioned by Joseph Bui (<a href="https://stackoverflow.com/questions/57471/c-graph-traversal-tracking-path-between-any-two-nodes#57509">57509</a>), but unless your states can be used (directly or indirectly) as indices to that array, you will need to use a hash function to map states to indices. In the latter case you might completely ignore certain states because they are mapped to the same index as a different (and seen) node, so you might want to be careful with this. Also, to get a path you still need to store the parent information which pretty much negates the use of the bit-array.</p>\n\n<p>The set of unvisited but seen nodes can be stored as a queue. (Bit arrays are of no use for this set because the array will be mostly empty and finding the next set bit is relatively expensive.)</p>\n'}, {'answer_id': 59257, 'author': 'Casey Watson', 'author_id': 4682, 'author_profile': 'https://Stackoverflow.com/users/4682', 'pm_score': 1, 'selected': False, 'text': '<p>I just submitted a solution <a href="https://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices#58446">over here</a> that also applies to this question.</p>\n\n<p>Basically, I just keep a single list (a stack really) of visited nodes. Add a node to the list just before recursing or saving a solution. Always remove from the list directly after.</p>\n'}, {'answer_id': 169408, 'author': 'smaclell', 'author_id': 22914, 'author_profile': 'https://Stackoverflow.com/users/22914', 'pm_score': 0, 'selected': False, 'text': '<p>If you are using .NET 3.5 consider using the <a href="http://msdn.microsoft.com/en-us/library/bb359438.aspx" rel="nofollow noreferrer">Hashset</a> to prevent duplicate nodes from being expanded, this happens when there is cycles in your graph. If you have any knowledge about the contents of the graph consider implementing an <a href="http://en.wikipedia.org/wiki/A*_search_algorithm" rel="nofollow noreferrer">A* search</a> to reduce the number of nodes that are expanded. Good luck and I hope it works out for you. </p>\n\n<p>If you are still a fan of treeware there are many excellent books on the topic of graphs and graph search such as Artificial Intelligence: A Modern Approach by Peter Norvig and  Stuart Russell.</p>\n\n<p>The links in my response appear to have a bug they are Hashset: <a href="http://msdn.com/en-us/library/bb359438.aspx" rel="nofollow noreferrer">http://msdn.com/en-us/library/bb359438.aspx</a> and A* search: <a href="http://en.wikipedia.org/wiki/A*_search_algorithm" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/A*_search_algorithm</a></p>\n'}]
['https://Stackoverflow.com/questions/57471', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/5964/']