为什么 BFS 的复杂度是 O(V+E) 而不是 O(E)？
Why is the complexity of BFS O(V+E) instead of O(E)?
这是一个通用的 BFS 实现：
对于具有 V 个节点和 E 边总数的连通图，我们知道在内循环中每条边都会被考虑两次。那么，如果 BFS 的 内循环 中的迭代总数将是 2 * number of edges E，那么运行时不是将是 O(E) 吗？
在这种情况下，需要更深入地了解一下实现。特别是如何判断一个节点是否被访问？
传统算法通过给顶点着色来做到这一点。所有的顶点一开始都是白色的，当它们被访问时会变成黑色。因此，访问可以简单地通过查看顶点的颜色来确定。如果你使用这种方法，那么你必须做 O(V) 的初始化工作，在开始时将每个顶点的颜色设置为白色。
你可以用不同的方式管理你的颜色。您可以维护一个包含所有已访问节点的数据结构。如果这样做，就可以避免 O(V) 初始化成本。但是，您将在数据结构的其他地方支付该费用。例如，如果您将它们全部存储在平衡树中，则每个 if w is not visited 现在的成本为 O(log V)。
这显然给了你一个选择。您可以使用传统的着色方法获得 O(V+E)，也可以通过将此信息存储在您自己的数据结构中获得 O(E log V)。
您在问题中指定了连通图。在这种情况下，O(V+E) == O(E) 因为顶点数永远不会超过 E+1。但是，BFS 的时间复杂度通常是针对任意图给出的，其中可以包括非常稀疏的图。
如果图足够稀疏（例如，一百万个顶点和五个边），则初始化成本可能大到您想要切换到 O(E ln V) 算法。然而，这些在实际环境中很少见。在实际设置中，传统方法（给每个顶点一种颜色）的速度与你选择这种传统着色方案的更花哨的数据结构相比是如此之快，除了最稀疏的图形之外的所有东西。
如果您在顶点上维护了专用颜色 属性，并且在算法调用之间所有节点都是黑色的不变规则，则可以通过对每个 BFS 执行两次来将成本降低到 O(E)。在你的第一遍中，你可以将它们全部设置为白色，然后进行第二遍将它们全部变成黑色。如果你有一个非常稀疏的图，这可能会更有效。
好吧，让我们把它分解成简单的部分...
您保留了一个已访问的数组，通过查找它，您决定是否将 push 一个 node 放入 queue 中。一旦访问过，您就不会再 push 了。因此，有多少节点被推入队列：(of course) V nodes。它的复杂度是 O(V)。
现在，每次，您从队列中取出 a node 并访问它的所有 neighboring nodes。现在，按照这种方式，for all of V nodes，你会遇到多少个节点。好吧，如果图形是 unidirectional，它就是 number of edges，或者，如果图形是 bidirectional，它就是 2 * number of edges。因此，unidirectional 的复杂度为 O(E)，bidirectional 的复杂度为 O(2 * E)。
因此，最终（即总）复杂度将是 O(V + E) 或 O(V + 2 * E) 或 generally，我们可以说 O(v + E).
因为可能存在边数少于顶点数的图形。
考虑这张图：
1 ---- 2
|
|
3 ---- 4
有4个顶点但只有3条边，在BFS中你必须遍历每一个顶点。这就是时间复杂度为 O(V+E) 的原因，因为它同时考虑了 V 和 E。
这是一个通用的 BFS 实现：
V 个节点和 E 边总数的连通图，我们知道在内循环中每条边都会被考虑两次。那么，如果 BFS 的 内循环 中的迭代总数将是 2 * number of edges E，那么运行时不是将是 O(E) 吗？
在这种情况下，需要更深入地了解一下实现。特别是如何判断一个节点是否被访问？
传统算法通过给顶点着色来做到这一点。所有的顶点一开始都是白色的，当它们被访问时会变成黑色。因此，访问可以简单地通过查看顶点的颜色来确定。如果你使用这种方法，那么你必须做 O(V) 的初始化工作，在开始时将每个顶点的颜色设置为白色。
你可以用不同的方式管理你的颜色。您可以维护一个包含所有已访问节点的数据结构。如果这样做，就可以避免 O(V) 初始化成本。但是，您将在数据结构的其他地方支付该费用。例如，如果您将它们全部存储在平衡树中，则每个 if w is not visited 现在的成本为 O(log V)。
这显然给了你一个选择。您可以使用传统的着色方法获得 O(V+E)，也可以通过将此信息存储在您自己的数据结构中获得 O(E log V)。
您在问题中指定了连通图。在这种情况下，O(V+E) == O(E) 因为顶点数永远不会超过 E+1。但是，BFS 的时间复杂度通常是针对任意图给出的，其中可以包括非常稀疏的图。
如果图足够稀疏（例如，一百万个顶点和五个边），则初始化成本可能大到您想要切换到 O(E ln V) 算法。然而，这些在实际环境中很少见。在实际设置中，传统方法（给每个顶点一种颜色）的速度与你选择这种传统着色方案的更花哨的数据结构相比是如此之快，除了最稀疏的图形之外的所有东西。
如果您在顶点上维护了专用颜色 属性，并且在算法调用之间所有节点都是黑色的不变规则，则可以通过对每个 BFS 执行两次来将成本降低到 O(E)。在你的第一遍中，你可以将它们全部设置为白色，然后进行第二遍将它们全部变成黑色。如果你有一个非常稀疏的图，这可能会更有效。
好吧，让我们把它分解成简单的部分...
您保留了一个已访问的数组，通过查找它，您决定是否将
push一个node放入queue中。一旦访问过，您就不会再push了。因此，有多少节点被推入队列：(of course) V nodes。它的复杂度是 O(V)。现在，每次，您从队列中取出
a node并访问它的所有neighboring nodes。现在，按照这种方式，for all of V nodes，你会遇到多少个节点。好吧，如果图形是unidirectional，它就是number of edges，或者，如果图形是bidirectional，它就是2 * number of edges。因此，unidirectional的复杂度为O(E)，bidirectional的复杂度为O(2 * E)。
因此，最终（即总）复杂度将是 O(V + E) 或 O(V + 2 * E) 或 generally，我们可以说 O(v + E).
因为可能存在边数少于顶点数的图形。 考虑这张图：
1 ---- 2
|
|
3 ---- 4
有4个顶点但只有3条边，在BFS中你必须遍历每一个顶点。这就是时间复杂度为 O(V+E) 的原因，因为它同时考虑了 V 和 E。