为什么BFS/DFS的时间复杂度不仅仅是O(E)，而是O(E+V)？

Question

我知道stackoverflow上有一个类似的问题，其中一个人问为什么BFS/DFS的时间复杂度不仅仅是O(V)。

给出的恰当答案是，在完全图的情况下，E可能达到V^2，因此将E计入时间复杂度是合理的。

但是，如果V不能大于E+1。那么，在这种情况下，不考虑V的时间复杂度应该也能够工作吧？

- Sandy

---

更多的人应该有这个问题，说实话。 - csguy

Answer 1

如果给定 E = kV + c，其中 k 和 c 是一些实常数，则：
O(E + V) = O(kV + c + V) = O(V) = O(E)，你的论证是正确的。

树是一个例子。

然而，在一般情况下（即没有任何先前信息），E = O(V^2)，因此我们不能比 O(V^2) 更好。 为什么不总是只写O(E)？ 编辑：始终编写 O(E + V) 的主要原因是为了避免歧义。

例如，可能存在图中根本没有边的情况（即 O(E) ~ O(1)）。即使对于这种情况，我们也必须转到每个顶点（O(V)），我们也无法在O(1)时间内完成。

因此，通常仅写 O(E) 不够。

- axiom

---

那么，对于广度优先搜索，我可以简单地说时间复杂度为O(E)吗？ - Sandy

只有在满足上述条件的情况下才会执行@Sandy。一般情况下可能没有边，但仍需访问每个顶点，因此我们写成 O(V + E)。 - axiom

当你无法通过边找到顶点时，如何“访问每个顶点”？该答案是不正确的。 - Matt Timmermans

@MattTimmermans for source in V: dfs(source)。在一张图中，如果|E|=0，这个循环的时间复杂度是多少？ - axiom

@MattTimmermans 我认为你可能在这里混淆了复杂性的概念。问题是：给定一个具有V个顶点和E条边的图形，运行BFS或DFS的时间复杂度将是多少？这不同于问：您能否构建一个图形，使得BFS需要O(1)的时间？该问题是关于最坏情况的。 - axiom

Answer 2

必须包含V，因为BFS和DFS都依赖于大小为|V|的数组来跟踪已处理/发现/探索的顶点（无论情况如何）。如果一个图有0条边和100000个顶点，这样的数组仍需要比只有5个顶点时更长时间进行初始化。因此，BFS和DFS的时间复杂度与|V|成比例。

- A K

---

你可以使用哈希表来实现BFS或DFS，而不是使用数组，这样初始化只需要O(1)的时间，而不是O(V)。 - kaya3

你的意思是将每个顶点插入哈希表中（即将其用作从顶点到布尔值的无序映射）吗？ - A K

哈希表中的键是已访问的顶点；当且仅当顶点存在于哈希表中时，它才被视为已访问。这样，您可以从空哈希表开始（即尚未访问任何顶点），而不必显式地将每个顶点标记为“尚未访问”。我认为哈希表是无序集合的实现，而不是映射，但如果存在不同的状态（例如，预访问与后访问），则映射可能更有用。 - kaya3

@kaya3，你的哈希表有多大？你初始化了吗？ :) 好的，如果你使用动态增长的哈希表，那么 BFS 的复杂度预计为 O(E) 而不是 O(V+E)。这只是不太常见的实现方式，并且有充分的理由。 - Matt Timmermans

@MattTimmermans 如果你使用高级语言编写代码，通常使用动态增长哈希表来实现BFS和DFS，因为这是内置集合类型的数据结构。例如，对于“深度优先搜索python”的前三个谷歌搜索结果中的两个，都会初始化visited = set()，链接在这里和这里。 - kaya3

@kaya3 是的，没错。 - Matt Timmermans