This question already has answers here:
Why is the time complexity of both DFS and BFS O( V + E )
（7个答案）
我正在尝试用java实现bfs和dfs作为一个通用算法。我正在编写一个方法，该方法返回作为字符串的算法的最坏情况复杂度。在DFS（和BFS）中，图中的每个节点只能访问一次在最坏的情况下，每个节点只访问一次。因此，为什么这些算法的复杂性是O（V+E）而不是O（V）？这里V是节点（或顶点）的数目，E是边的数目。
（7个答案）
我正在尝试用java实现bfs和dfs作为一个通用算法。我正在编写一个方法，该方法返回作为字符串的算法的最坏情况复杂度。在DFS（和BFS）中，图中的每个节点只能访问一次在最坏的情况下，每个节点只访问一次。因此，为什么这些算法的复杂性是O（V+E）而不是O（V）？这里V是节点（或顶点）的数目，E是边的数目。
最佳答案
树遍历（bfs和dfs）是o（v+e），因为每个边必须精确遍历一次，每个节点必须精确访问一次。树遍历通常是一种帮助我们查看问题的抽象。在大多数简单的情况下，v和e都是微不足道的操作，但情况并非总是如此，v的效率可能与e有着根本的不同。例如，遍历一条边可以像跟踪一个指针一样简单，或者它可能要求您通过网络从远程主机获取数据（可能涉及昂贵的数据库查询）访问一个节点可以像设置布尔值一样简单，也可以涉及到对该节点上的数据执行一些昂贵的计算。
O（V + E）提醒我们，当我们考虑遍历树的整体复杂性时，必须考虑访问节点的复杂性和遍历边缘的复杂性。