我必须用BFS实现邻接矩阵吗？

Question

我试图使用队列实现BFS算法，我不想为了学习目的寻找任何在线代码。我所做的只是遵循算法，并尝试实现它。我有一个关于邻接矩阵(图的数据结构)的问题。

我知道一个常见的图形数据结构是邻接矩阵。所以，我在这里的问题是，我是否必须与BFS算法一起实现邻接矩阵，还是没关系。

我真的很困惑。让我困惑的事情之一，图形的数据，如果没有数据结构，这些数据应该存储在哪里？

由衷地

Answer 1

选择数据结构的最佳方法是操作。有了一个完整的操作列表，评估实现wrt标准对问题很重要:空间、速度、代码大小等等。

对于BFS，操作非常简单：

Set<Node> getSources(Graph graph) // all in graph with no in-edges
Set<Node> getNeighbors(Node node) // all reachable from node by out-edges

现在，我们可以根据节点的n=number来评估图形数据结构选项：

• 邻接矩阵：
  • getSources是O(n^2)时间
  • getNeighbors是O(n)时间

​

• 邻接列表向量(单独)：
  • getSources是O(n)时间
  • getNeighbors是O(1)时间

​

• 邻接列表的“聪明”向量：
  • getSources是O(1)时间
  • getNeighbors是O(1)时间

​

聪明之处只是在图的构造过程中维护源集，因此成本由边插入来摊销。也就是说，在创建节点时，将其添加到源列表中，因为它没有外边。在添加边缘时，从源集中移除to节点。

现在，您可以根据运行时做出明智的选择。同样的，对于空间，简单，或任何其他的考虑因素正在发挥作用。然后选择并实施。

Answer 2

广度优先搜索假设你有某种方式来表示你正在使用的图形结构，它的效率取决于你所拥有的表示的选择，但是你没有被限制使用一个邻接矩阵。BFS的许多实现都以某种方式隐式地表示了图形(例如，作为存储迷宫或某种游戏的2D数组)，并且工作得很好。您也可以使用邻接列表，这对于我们在BFS中特别有效。

您将要编写的特定代码将取决于图形是如何表示的，但不要觉得只能用一种方式来完成它。选择最适合您的应用程序。