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

Question

寻找一种很好的方法来跟踪两个节点之间的广度优先遍历，而无需对图一无所知。与深度优先（如果路径不成功，您可以丢弃路径）相比，您在遍历过程中可能有很多“开放”的可能性。

Answer 1

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

Answer 2

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

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

未访问但已看到的节点集可以存储为队列。（位数组对这个集合没有用，因为数组大部分是空的，并且找到下一个集合位相对昂贵。）

Answer 3

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

基本上，我只保留一个访问节点的列表（实际上是一个堆栈）。在递归或保存解决方案之前将节点添加到列表中。之后总是直接从列表中删除。

Answer 4

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

如果您仍然是树件的粉丝，那么有很多关于图和图搜索主题的优秀书籍，例如 Peter Norvig 和 Stuart Russell 的《人工智能：现代方法》。

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