BFS的时间复杂度分析

Question

我知道有很多关于BFS时间复杂度的问题，即：O（V + E）。然而，我仍然难以理解为什么时间复杂度是O（V + E），而不是O（V * E）。我知道O（V + E）代表O（max [V，E]），我唯一的猜测是它与图的密度有关，而不是算法本身，例如归并排序，其时间复杂度始终为O（n * logn）。我想到的例子是：1.具有| E | = | V | - 1的有向图，时间复杂度将为O（V）；2.具有| E | = | V | * | V-1 |的有向图，实际上复杂度将为O（| E |）= O（| V | * | V |），因为每个顶点都有一个指向除自身以外的每个其他顶点的出边。我方向正确吗？任何见解都将非常有帮助。

- RookieCookie

Answer 1

你的"思考示例"表明复杂度不是O(V*E)，而是O(E)。当图连接时，你总可以说它是O(E)。将V包括在时间复杂度中的原因是为了涵盖具有比边更多的顶点（因此是不连通的）的图：BFS算法不仅必须访问所有边，还必须访问所有顶点，包括没有边的顶点，只是为了检测它们没有边。因此我们必须说O(V+E)。

- trincot

---

我的例子是为了支持O(V+E)的复杂度，但非常感谢你理解了！ - RookieCookie

你知道如果使用邻接矩阵会增加多少复杂性吗？ - roadev

@raodev，那将是O（V²），即矩阵的大小。如果您对此有疑问，请发布一个新问题。 - trincot

Answer 2

如果你按照算法走，复杂性就会很容易理解。令Q为FIFO队列，最初包含源节点。BFS基本上执行以下操作：

while Q not empty
  pop u from Q
  for each adjacency v of u
     if v is not marked
         mark v
         push v into Q

由于每个节点只添加一次并删除一次，所以 while 循环执行了 O(V) 次。每当我们弹出 u 时，我们执行 |adj[u]| 次操作，其中 |adj[u]| 是 u 的邻接数。

因此，总复杂度为对所有 V 的 Sum (1+|adj[u]|)，这是 O(V+E)，因为邻接数之和是 O(E)（对于无向图是 2E，对于有向图是 E）。

- Hikmat Farhat

Answer 3

这取决于邻接表的实现方式。一个正确实现的邻接表是一个顶点的列表/数组，每个顶点条目都附有一组相关边。

关键在于边的条目直接指向它们对应的顶点数组/列表条目，它们永远不需要在顶点数组/列表中搜索匹配的条目，只需直接查找即可。这确保了总边访问次数为2E，总顶点访问次数为V+2E。这使得总时间复杂度为O(E+V)。

在错误实现的邻接表中，顶点数组/列表没有直接索引，因此从边条目到顶点条目的转换需要在顶点列表中进行搜索，其时间复杂度为O(V)，这意味着总时间复杂度为O(E*V)。

- RBarryYoung

Answer 4

考虑一种情况，当你有一棵树时，甚至可能带有循环，你从根节点开始搜索，目标是树的最后一个叶子节点。在这种情况下，你需要遍历所有的边，直到到达目的地。

例如：

0 - 1
1 - 2
0 - 2
0 - 3

在这种情况下，你需要在找到节点#3之前检查4个边缘。

- Azamat Zhurtbayev