bfs
- 邻接表存储 O(V + M)
每个顶点需要访问一次,访问每个顶点时,其所有邻边需要访问一次
- 邻接矩阵存储 O(V^2)
每个顶点需要访问一次,而访问每个顶点的邻边需要O(V)
dfs
DFS算法是一一个递归算法,需要借助一个递归工作栈,故它的空问复杂度为O(V)。
遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所采用结构。
邻接表表示时,查找所有顶点的邻接点所需时间为O(E),访问顶点的邻接点所花时间为O(V),
此时,总的时间复杂度为O(V+E)。
邻接矩阵表示时,查找每个顶点的邻接点所需时间为O(V),要查找整个矩阵,故总的时间度为O(V^2)。
v为图的顶点数,E为边数。