本站http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html描述了当使用邻接表时，DFS和BFS的复杂度为O(V+E)，如果使用邻接矩阵，则复杂度为O(V2)。为什么是这样？
最佳答案
在这两种情况下，运行时间取决于遍历给定节点的传出边缘所需的时间。使用邻接表，运行时间与传出边的数量成正比。由于每个节点被访问一次，成本是节点数加上边数，即 O(m + n)。对于 am 邻接矩阵，找到所有出边所需的时间是 O(n)，因为必须检查节点行中的所有 n 列。对所有 n 个节点求和，结果为 O(n2)。
希望这可以帮助!
关于data-structures - 为什么 DFS 和 BFS 的时间复杂度取决于图的表示方式？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23925009/