寻找一种很好的方法来跟踪两个节点之间的广度优先遍历，而又不了解任何图形。相对于"深度优先"(如果没有平移，我们可以在其中丢弃路径)在遍历期间可能有很多"开放"的可能性。

解决方案

回答

天真的方法是用源节点作为根，其所有连接作为其子节点来构建树。根据我们拥有的空间量，我们可能需要消除循环的时间。我们可以使用位图来做到这一点，其中每个位对应于图中的一个不同节点。当我们到达目标节点时，可以跟随父链接回到根，这就是路径。由于首先要广度，因此即使我们没有消除循环，也可以确保这是一条最短的路径。

回答

对于广度优先搜索，我们至少需要存储两件事。一个是已经访问过的节点的集合，另一个是可以从访问的节点直接访问但自身不访问的节点的集合。然后，我们将状态从后者设置为移动到前者，将新可访问的状态添加到后者。如果我们需要从根到某些节点的路径，则还需要为上述集合中的每个节点(根除外)存储一个父节点。

通常，访问节点集和未访问子节点集(即可见节点集)的并集存储在哈希表中。这是为了能够快速确定之前是否已经看到过"新"状态，并且在这种情况下可以忽略它。如果状态数量很多，则可能确实需要一个位数组(如Joseph Bui(57509)所述)，但是除非状态可以(直接或者间接)用作该数组的索引，否则我们将需要使用哈希用于将状态映射到索引的函数。在后一种情况下，我们可能会完全忽略某些状态，因为它们被映射到与其他(可见)节点相同的索引，因此我们可能需要谨慎行事。我们仍然需要存储父信息，这几乎抵消了位数组的使用。

一组未访问但可见的节点可以存储为队列。 (位数组对此集没有用，因为该数组将大部分为空，并且查找下一个设置位相对昂贵。)

回答

我刚刚在这里提交了一个解决方案，该解决方案也适用于此问题。

基本上，我只保留一个已访问节点的列表(实际上是一个堆栈)。在递归或者保存解决方案之前，将节点添加到列表中。总是在此之后立即将其从列表中删除。

回答

如果使用的是.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