如何构造适合bfs的邻接表数据结构

本文关键字：数据结构 bfs 何构造 | 更新日期: 2023-09-27 18:07:19

关于建立和搜索邻接树的面试问题，但我以前从未使用过它们，所以我不确定从哪里开始。

我有一个文件包含如下数据:

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。

然后我需要计算两个节点之间的最短路径(这两个节点在问题中指定)。然后，我需要用大0符号提供估计的复杂度。

后一个我可能可以糊弄，尽管我直到现在才听说它，维基百科并没有帮助我理解如何将搜索功能分解成大o，但我以后会担心的(除非有人有好的链接他们可以分享)。

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

有很多搜索的例子，所以我可能会对这部分进行分类，但任何有助于启动数据模型的帮助，将适合从数据文件加载并适合bfs搜索(或者，如果有更好的搜索选项，请教我)，将是很大的帮助。

如何构造适合bfs的邻接表数据结构

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

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

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

-- 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价值时,你才能够退出队列是空的,你只会被推节点到节点的队列,如果你从来没有(它不会存在于短路径列表),或者你已经发现了这种新方法的有比过去的短(现在你要重新计算节点的最短的距离你可以从这个节点)。

相关文章：