为什么BFS的复杂度是O(V + E)而不是O(E)? [英] Why is the complexity of BFS O(V+E) instead of O(E)?

问题描述

这是通用的BFS实现:

This is a generic BFS implementation:

对于具有V个节点和E个边总数的连接图，我们知道在内部循环中每个边都将被考虑两次.因此，如果BFS的内部循环中的迭代总数将为2 * number of edges E，那么运行时是否将变为O(E)?

For a connected graph with V nodes and E total number of edges, we know that every edge will be considered twice in the inner loop. So if the total number of iterations in the inner loop of BFS is going to be 2 * number of edges E, isn't the runtime going to be O(E) instead?

推荐答案

在这种情况下，需要深入了解实现.特别是，如何确定是否访问了节点?

This is a case where one needs to look a little deeper at the implementation. In particular, how do I determine if a node is visited or not?

传统算法是通过为顶点着色来实现的.首先，所有顶点都被着色为白色，而被访问时它们将被着色为黑色.因此可以简单地通过查看顶点的颜色来确定访问.如果使用这种方法，则必须进行价值O(V)的初始化工作，并将每个顶点的颜色从一开始就设置为白色.

The traditional algorithm does this by coloring the vertices. All vertices are colored white at first, and they get colored black as they are visited. Thus visitation can be determined simply by looking at the color of the vertex. If you use this approach, then you have to do O(V) worth of initialization work setting the color of each vertex to white at the start.

您可以不同地管理颜色.您可以维护一个包含所有已访问节点的数据结构.如果这样做，则可以避免O(V)初始化成本.但是，您将在数据结构中的其他地方支付该费用.例如，如果将它们全部存储在平衡树中，则每个if w is not visited现在的成本为O(log V).

You could manage your colors differently. You could maintain a data structure containing all visited nodes. If you did this, you could avoid the O(V) initialization cost. However, you will pay that cost elsewhere in the data structure. For example, if you stored them all in a balanced tree, each if w is not visited now costs O(log V).

这显然给了您一个选择.您可以使用传统的着色方法获得O(V + E)，也可以通过将该信息存储在自己的数据结构中来获得O(E log V).

This obviously gives you a choice. You can have O(V+E) using the traditional coloring approach, or you can have O(E log V) by storing this information in your own data structure.

您在问题中指定一个连接图.在这种情况下，O(V + E)== O(E)，因为顶点的数量永远不能超过E + 1.但是，BFS的时间复杂度通常是针对任意图给出的，该图可能包含非常稀疏的图.

You specify a connected graph in your problem. In this case, O(V+E) == O(E) because the number of vertices can never be more than E+1. However, the time complexity of BFS is typically given with respect to an arbitrary graph, which can include a very sparse graph.

如果图足够稀疏(例如，一百万个顶点和五个边)，则初始化的成本可能会很高，以至于您想切换到O(E ln V)算法.但是，这些在实际环境中很少见.在实际情况下，与更精美的数据结构相比，传统方法(为每个顶点赋予颜色)的速度是如此之快，以至于您为所有事物(除了最稀疏的图形之外)都选择了这种传统的着色方案.

If a graph is sufficiently sparse (say, a million vertices and five edges), the cost of initialization may be great enough that you want to switch to a O(E ln V) algorithm. However, these are pretty rare in a practical setting. In a practical setting, the speed of the traditional approach (giving each vertex a color) is just so blinding fast compared to the more fancy data structures that you choose this traditional coloring scheme for everything except the most extraordinarily sparse graphs.

如果您通过不变的规则在顶点上维护专用的颜色属性，即所有算法在两次调用之间都是黑色的，则可以通过对每个BFS进行两次操作来将成本降低到O(E).在第一次通过时，您可以将它们全部设置为白色，然后再进行第二次通过以将它们全部变为黑色.如果您的图表非常稀疏，这可能会更有效.

If you maintained a dedicated color property on your vertices with an invariant rule that all nodes are black between algotihm invocations, you could drop the cost to O(E) by doing each BFS twice. On your first pass, you could set them all to white, and then do a second pass to turn them all black. If you had a very sparse graph, this could be more efficient.

这篇关于为什么BFS的复杂度是O(V + E)而不是O(E)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！