我正在尝试使用队列实现BFS算法，我不想为了学习目的而寻找任何在线代码。我所做的只是遵循算法并尝试实现它。我有一个关于邻接矩阵（图的数据结构）的问题。
我知道一种常见的图数据结构是邻接矩阵。所以，我的问题是，我必须和BFS算法一起实现邻接矩阵吗？或者这无关紧要。
我真的很困惑。让我困惑的一件事是，图形的数据，如果没有数据结构，这些数据应该存储在哪里？
真诚的
广度优先搜索假设您有某种方式来表示正在使用的图结构，其效率取决于您所选择的表示方式，但您不必使用邻接矩阵。BFS的许多实现都以某种方式隐式地表示图形（例如，作为存储迷宫的2D阵列或某种游戏），并且工作得很好。你也可以使用邻接列表，这对我们在BFS中特别有效。
您将要编写的特定代码将取决于图形的表示方式，但不要觉得只能用一种方式。选择最适合您应用程序的选项。
选择数据结构的最佳方式是操作。有了一个完整的操作列表，评估实现对问题很重要的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=节点数量来评估图数据结构选项：
- 相邻矩阵：
- getSources是O（n^2）时间
- getNeighbors是O（n）时间
- 邻接列表的矢量（单独）：
- getSources是O（n）时间
- getNeighbors是O（1）时间
- 邻接列表的"聪明"矢量：
- getSources是O（1）时间
- getNeighbors是O（1）时间
聪明之处在于，在构建图时只需维护源集，因此通过插入边来分摊成本。也就是说，在创建节点时，将其添加到源列表中，因为它没有外边缘。添加边时，请从源集中删除到节点。
现在，您可以根据运行时间做出明智的选择。为了空间、简单性或其他考虑因素，也要这样做。然后选择并执行。