为什么BFS的复杂度是O(V+E)而不是O(E)？

Question

这是一个通用的 BFS 实现：

V对于具有节点和总边数的 连通图E，我们知道每条边在内循环中都会被考虑两次。那么，如果 BFS内循环的迭代总数为2 * number of edges E，那么运行时间不是会是O(E)吗？

Answer 1

在这种情况下，人们需要更深入地了解实施情况。特别是，如何确定节点是否被访问？

传统算法通过对顶点着色来实现这一点。所有顶点一开始都是白色的，当它们被访问时，它们就会变成黑色。因此，只需查看顶点的颜色即可确定访问情况。如果您使用这种方法，那么您必须执行 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)。在第一次通过时，您可以将它们全部设置为白色，然后进行第二次通过将它们全部设置为黑色。如果你有一个非常稀疏的图，这可能会更有效。