我正在尝试在 Java 中实现 BFS 和 DFS 作为通用算法。我正在编写一种getComplexity()将算法的最坏情况复杂度作为字符串返回的方法。在 DFS（和 BFS）中，图中的每个节点只能被访问一次。在最坏的情况下，每个节点只被访问一次。因此，为什么这些算法的复杂度是 O(V+E) 而不是 O(V)？这里 V 是节点（或顶点）的数量，E 是边的数量。
问问题
662 次
2 回答
4
Tree traversal (BFS and DFS) is O(V + E) because each edge must be traversed exactly once and each node must be visited exactly once. Tree traversal is often an abstraction that helps give us a view on a problem. In most simple cases, both V and E are trivial operations, however this is not always the case and the efficiency of V could be radically different from E. For instance, traversing an edge could be as simple as following a pointer, or it might require you to fetch data from a remote host over a network (possibly involving an expensive database query). Visiting a node could be as simple as setting a boolean value, or it could involve performing some expensive computations on the data at that node.
O(V + E) reminds us that we must take into consideration both the complexity of visiting nodes and of traversing edges when we reason about the overall complexity of traversing a tree.
于 2013-10-03T04:08:42.473 回答
1
因为在一般的图中，E（即边的数量）可以和V*(V-1)/2（对于完全图）一样大，其数量级为V^2. 所以我们不能忽略我们需要检查每条边的事实（为了找到未访问的节点），因为检查V^2的成本可能比访问每个节点的成本更高（正如我所说，它可能是）总是V）。
于 2013-10-03T05:09:35.283 回答