邻接表表示时，查找所有顶点的邻接点所需时间为，访问顶点的邻接点所花时间为，此时，总的时间复杂度为。深度优先搜索的时间复杂度也是；

由于每个节点仅被发现一次，因此每个节点入栈和出栈各一次，时间均为，故入栈和出栈总时间为；由于需要对每个节点的邻接表进行扫描，时间为，总时间为；综上所示，广度优先搜索的时间复杂度为。

邻接矩阵表示时，查找每个顶点的邻接点所需时间为，要查找整个矩阵，故深度优先搜索与广度优先搜索的时间复杂度均为。