1

关于构建和搜索邻接树的面试问题，但我以前从未与他们合作过，所以我不确定从哪里开始。

我有一个包含以下数据的文件：

2 13556 225 235
225 2212 226
2212 8888 2213
8888 144115 72629 141336 8889 146090 129948 167357
144115 160496 163089 144114 144116
...

格式如下：

<parent node> <child node> [ <child node> [ …] ]

每条边的长度为 1。

然后我需要计算两个节点之间的最短路径（这两个在问题中指定）。然后，我需要以大 O 表示法提供估计的复杂度。

后者我可能会捏造，尽管直到现在我什至从未听说过它，而且在理解如何将搜索功能分解为大 O 方面，维基百科对我没有多大帮助，但我稍后会担心（除非有人有一个很好的链接可以分享）。

我现在关心的是尝试对这些数据进行建模，然后搜索最短路径。就像我说的，我以前从未使用过这种结构，所以我什至不知道从哪里开始。我在这里发现了关于邻接列表的另一个问题，但它似乎并不是我想要的，除非我完全没有抓住重点。在我看来，输入数据需要重新组织以满足该问题中使用的结构，而我正在从文件中读取我的数据，所以我认为我需要遍历每个节点和节点列表确定我是否已经输入了父母，这可能需要很长时间。我也看不到如何使用该结构创建 bfs 搜索。

那里有很多搜索示例，所以我可能会整理出那部分，但是在启动数据模型方面的任何帮助都适合从数据文件加载并适合 bfs 搜索（或者，如果有那里有更好的搜索选项，请教我），会有很大的帮助。

4

1 回答 1

1

您可能希望将此数据存储在HashTable<int, List<int>>（字典）（链接）中，键为 int (NodeID)，值为List<int>，其中这些是作为键的节点的可能目的地。

您需要另一个HashTable<int, int>(ShortestPathLastStep)，它将存储两个 NodeID。这将代表到达给定节点的最短路径的最后一步。您需要它才能回放最短路径。

要执行 BFS（广度优先搜索），您将使用Queue<int>(bfsQueue)。将开始节点（在您的问题中给出）推送到队列中。现在执行以下算法

-- currentNodeID = pop bfsQueue
---- children = Links[NodeID]
------ foreach (childNodeID in children)
--------- if (childNodeID == destinationNodeID)
----------- exit and playback shortest path
----------if (!ShortestPathLastStep.contains(childNodeID))
------------ ShortestPathLastStep.Add(childNodeID, currentNodeID);
----------bfsQueue.Push(childNodeID);
----------goto first line

该解决方案假设在任何两个节点之间的旅行是一个恒定的成本。它是 BFS 的理想选择，因为当您第一次到达目的地时，您将采用最短路径（如果链接长度可变，则不是这样）。如果链接不是恒定长度，则在决定覆盖 ShortestPathLastStep 值时必须添加更多逻辑，在队列为 EMPTY 之前，您将无法退出，并且您只会将节点推送到队列中从未去过该节点（它不会出现在短路径列表中），或者您发现这种到达那里的新方式比到达那里的最后一种方式更短（现在您必须重新计算节点的最短距离您可以从此节点访问）。

于 2013-04-02T21:54:27.030 回答