C＃图遍历 - 任意两个节点之间的跟踪路径

Question

寻找一种很好的方法来跟踪两个节点之间的宽度优先遍历，而无需了解任何关于该图的信息。与深度优先（如果它不能平移的话，你可以扔掉路径），在遍历过程中你可能会有很多“开放”的可能性。

Answer 1

幼稚的方法是建立一个以源节点为根，其所有连接为子节点的树。根据您拥有的空间大小，您可能需要随时消除周期。您可以使用位图来实现这一点，其中每个位对应图中的不同节点。当您到达目标节点时，您可以按照父链接回到根目录，那就是您的路径。由于您首先考虑的是宽度，即使您没有消除周期，也可以确信它是最短的路径。

Answer 2

对于广度优先搜索，您至少需要存储两件事。一个是已经访问过的节点集合，另一个是从访问节点直接访问但不能访问的节点集合。然后你保持移动状态从后者到前者，为后者添加新的可达状态。如果你需要从根到某个节点有一条路径，那么你还需要为上述集合中的每个节点（根除外）存储一个父节点。

通常，访问节点集合和未访问子节点集合（即，所看到节点集合）的并集存储在散列表中。这是为了能够快速确定之前是否已经看到“新”状态，并且如果是这种情况，则忽略它。如果你的状态真的很多，你可能确实需要一个位数组（如Joseph Bui所提到的（57509），但是除非你的状态可以直接或间接地用作该数组的索引，否则你需要使用散列函数将状态映射到索引，在后一种情况下，您可能会完全忽略某些状态，因为它们映射到与另一个（和可见）节点相同的索引，因此您可能需要小心这一点。另外，要获取路径你仍然需要存储父信息，这几乎否定了位阵列的使用

未访问但可见节点的集合可以存储为一个队列（位数组对这个集合没有用处，因为阵列将大部分为空，并且发现下一个设置位相对昂贵。）

Answer 3

我刚刚提交了一个解决方案over here也适用于这个问题。

基本上，我只保留访问节点的单个列表（真正的堆栈）。在递归或保存解决方案之前，将节点添加到列表中。之后，请务必从列表中删除。

Answer 4

如果您使用的是.NET 3.5，请考虑使用Hashset来防止重复节点被展开，这种情况发生在图形中有周期时发生。如果您对图表内容有任何了解，请考虑实施A* search以减少展开的节点数量。祝你好运，我希望它适合你。

如果你仍然是一个树型工具的爱好者，那么关于图形和图形搜索的话题有很多优秀的书籍，比如Peter Norvig和Stuart Russell的“人工智能：现代方法”。

在我的回应中的链接似乎有一个bug，他们的Hashset是：http://msdn.com/en-us/library/bb359438.aspx和A *搜索：http://en.wikipedia.org/wiki/A*_search_algorithm