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

Question

网站http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html描述了当使用邻接列表时,DFS和BFS具有复杂度O(V + E),如果使用邻接矩阵,复杂度为O(V ²).为什么是这样？

Answer 1

在这两种情况下,运行时都取决于迭代给定节点的传出边所需的时间.使用邻接列表,运行时与传出边的数量成正比.由于每个节点被访问一次,因此成本是节点数加上边数,即O(m + n).使用am邻接矩阵,找到所有输出边所需的时间是O(n),因为必须检查节点的行中的所有n列.总结所有n个节点,这可以得到O(n ²).

希望这可以帮助!

Answer 2

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

迭代每个顶点一次及其对应的事件边，所以总时间复杂度为 ->

时间复杂度 = v1 + (incident_edges on v1) + v2 + (incident_edges on v2) + ...... + vn + (incident_edges on 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)