为什么DFS和BFS的时间复杂度取决于图的表示方式？

Question

该网站http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html说明，当使用邻接表时，深度优先搜索和广度优先搜索的复杂度为O(V+E)，而如果使用邻接矩阵，则复杂度为O(V²)。为什么会这样呢？

- Nitish Jain

---

这个问题似乎不适合讨论，因为它与计算机程序或编程语言无关。 - Lightness Races in Orbit

^ 哈哈，真的吗？ - csguy

网络存档链接：https://web.archive.org/web/20190315040815/http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html - Tyler Chong

Answer 1

无论哪种情况，运行时间都取决于遍历给定节点的出边需要多长时间。使用邻接表，运行时间与出边数量成正比。由于每个节点只被访问一次，所以成本是节点数加上边数，即O(m + n)。使用邻接矩阵，查找所有出边所需的时间为O(n)，因为必须检查节点行中的所有n列。总结所有n个节点，这将得到O(n²)。希望这可以帮助您！

- templatetypedef

---

非常感谢，我明白了...我之前很困惑，因为维基百科上邻接表的空间复杂度被描述为O(n+m)，邻接矩阵则是O(n^2)，但时间复杂度却都是O(n+m)... - Nitish Jain

@templatetypedef 能否帮忙看一下这个问题？https://stackoverflow.com/questions/63321659/why-is-the-complexity-of-bfs-ove-instead-of-oe - csguy

Answer 2

DFS和BFS的时间复杂度可以如下计算:

遍历每个顶点一次及其相应的关联边，因此总时间复杂度为 -> 时间复杂度 = v1 + (v1的关联边) + v2 + (v2的关联边) + ...... + vn + (vn的关联边)

现在可以重新组合为 -> (v1+v2+v3+.....vn) + (v1的关联边 + v2的关联边 + ..... vn的关联边)

因此，总时间复杂度将变为 = (v1+v2+v3+.....vn) + (v1的关联边 + v2的关联边 + ..... vn的关联边)

(v1 + v2 + ... + vn) = V或n（顶点总数）

对于邻接表表示法:

(v1的关联边 + v2的关联边 + ..... vn的关联边) = E（边的总数）

因此，对于邻接表表示法，时间复杂度为O(V+E)

对于邻接矩阵表示法：

要访问相应节点（行）的相邻节点，我们需要迭代该行的所有列，这相当于V

因此，(v1的关联边 + v2的关联边 + ..... vn的关联边) = V + V + ....共V次V) = V * V

因此，时间复杂度为O(V + V^2) = O(V^2)

- Vimal

---

因此，时间复杂度将为O（V + V ^ 2）= O（V ^ 2），这是关键。 - Nitish Upreti

一个非常好的解释。 - mrinali

Answer 3

你必须注意到，对于每个顶点的探索所需的时间仅等于c*x，其中x是该顶点的入度。由于我们对整体复杂性感兴趣，整体时间将是c1*x1+c2*x2...cnxn（n个节点）的总和。取max(ci)=d，我们可以看出整体时间<=d（所有顶点的入度之和）=d*2m=O(m)。这里我们计算的不仅是一个顶点的时间，而是所有顶点一起计算的。但是入队操作需要O(n)的时间，因此总体时间为O(n+m)。

- user7011329