C#图遍历——跟踪任意两个节点之间的路径
寻找一种好方法来跟踪两个节点之间的广度优先遍历，而无需了解有关图的任何信息。 与深度优先（如果路径不成功，您可以丢弃该路径）相比，您在遍历过程中可能有很多“开放”的可能性。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果您使用 .NET 3.5，请考虑使用 哈希集 来防止重复节点被扩展，当图中存在循环时就会发生这种情况。 如果您对图表的内容有任何了解，请考虑实施 A* 搜索减少扩展的节点数量。 祝你好运，我希望它对你有用。
如果您仍然是树件的粉丝，那么有许多关于图形和图形搜索主题的优秀书籍，例如 Peter Norvig 和 Stuart Russell 的《人工智能：现代方法》。
我的回复中的链接似乎有一个错误，它们是哈希集：http://msdn。 com/en-us/library/bb359438.aspx 和 A* 搜索：http: //en.wikipedia.org/wiki/A*_search_algorithm
If you are using .NET 3.5 consider using the Hashset 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* search to reduce the number of nodes that are expanded. Good luck and I hope it works out for you.
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.
The links in my response appear to have a bug they are Hashset: http://msdn.com/en-us/library/bb359438.aspx and A* search: http://en.wikipedia.org/wiki/A*_search_algorithm
最简单的方法是构建一棵树，以源节点作为根，将其所有连接作为子节点。 根据您拥有的空间量，您可能需要随时消除循环。 您可以使用位图来做到这一点，其中每个位对应于图中的不同节点。 当您到达目标节点时，您可以沿着父链接回到根节点，这就是您的路径。 由于您首先选择广度，因此即使您不消除环路，也可以确保它是最短路径。
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.
对于广度优先搜索，您需要存储至少两件事。 一个是已经访问过的节点的集合，另一个是从访问过的节点可以直接到达但自身未被访问过的节点的集合。 然后，您不断将状态从后一组移动到前一组，并向后者添加新的可达状态。 如果您需要从根到某些节点的路径，那么您还需要为上述集合中的每个节点（根除外）存储一个父节点。
通常，访问过的节点集合和未访问过的子节点集合（即见过的节点集合）的并集存储在哈希表中。 这是为了能够快速确定以前是否见过“新”状态，如果是这种情况则忽略它。 如果你有大量的状态，你可能确实需要一个位数组（正如 Joseph Bui 提到的（57509），但除非您的状态可以（直接或间接）用作该数组的索引，否则您将需要使用哈希函数将状态映射到索引。在后一种情况下，您可能完全忽略某些状态，因为它们被映射到与不同（和看到的）节点相同的索引，因此您可能需要小心这一点此外，要获取路径，您仍然需要存储父信息。这几乎否定了位数组的使用。
未访问但已看到的节点集可以存储为队列（位数组对此集没有用处，因为该数组大部分为空，并且查找下一个集合位是。相对较贵。）
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.
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 (57509), 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.
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.)
我刚刚提交了一个解决方案在这里 这也适用于这个问题。
基本上，我只保留一个已访问节点的列表（实际上是一个堆栈）。 在递归或保存解决方案之前将节点添加到列表中。 之后始终立即从列表中删除。
I just submitted a solution over here that also applies to this question.
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.