<分区>
我正在尝试将 BFS 和 DFS 作为通用算法在 Java 中实现。我正在编写一个方法 getComplexity()，它将算法的最坏情况复杂度作为字符串返回。在 DFS(和 BFS)中，图中的每个节点只能被访问一次。在最坏的情况下，每个节点只被访问一次。因此，为什么这些算法的复杂度是 O(V+E) 而不是 O(V)？这里 V 是节点(或顶点)的数量，E 是边的数量。
<分区>
我正在尝试将 BFS 和 DFS 作为通用算法在 Java 中实现。我正在编写一个方法 getComplexity()，它将算法的最坏情况复杂度作为字符串返回。在 DFS(和 BFS)中，图中的每个节点只能被访问一次。在最坏的情况下，每个节点只被访问一次。因此，为什么这些算法的复杂度是 O(V+E) 而不是 O(V)？这里 V 是节点(或顶点)的数量，E 是边的数量。
最佳答案
树遍历(BFS 和 DFS)是 O(V + E)，因为每条边必须恰好遍历一次，每个节点必须恰好访问一次。树遍历通常是一种抽象，可以帮助我们了解问题。在大多数简单的情况下，V 和 E 都是微不足道的操作，但情况并非总是如此，V 的效率可能与 E 截然不同。例如，遍历边可以像跟随指针一样简单，或者它可能要求您通过网络从远程主机获取数据(可能涉及昂贵的数据库查询)。访问一个节点可以像设置一个 boolean 值一样简单，也可以涉及对该节点的数据执行一些昂贵的计算。
O(V + E) 提醒我们，在推理遍历树的整体复杂性时，必须同时考虑访问节点和遍历边的复杂性。
关于java - 为什么 DFS 和 BFS 的复杂度不是 O(V)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19150437/