在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为：

在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为 $O(V+E)$，其中 $V$ 是图的顶点数，$E$ 是图的边数。

深度优先遍历算法的时间复杂度与图的具体形态有关，但是在一般情况下，每个顶点会被访问且仅被访问一次，每条边也只会被访问一次。在邻接表表示法中，每个顶点的邻接点数不超过 $E$，所以访问每个顶点和它的邻接点的时间复杂度是 $O(E)$。因此，整个深度优先遍历算法的时间复杂度是 $O(V+E)$。

需要注意的是，这个时间复杂度是在每个顶点和每条边的访问操作的时间复杂度为 $O(1)$ 的情况下得出的。如果每个顶点和每条边的访问操作的时间复杂度不同，那么深度优先遍历算法的时间复杂度就需要按照具体情况进行分析。

相关问题

邻接表的深度优先遍历时间复杂度

邻接表是一种常用的图的表示方法，深度优先遍历（DFS）是一种图的遍历算法。在邻接表中，每个顶点都对应一个链表，链表中存储了与该顶点相邻的其他顶点。

深度优先遍历的时间复杂度取决于图的规模和结构。假设图有V个顶点和E条边，邻接表的时间复杂度为O(V+E)。

在深度优先遍历中，我们从一个起始顶点开始，递归地访问其相邻顶点，并继续递归地访问相邻顶点的相邻顶点，直到所有可达的顶点都被访问到为止。在邻接表中，每个顶点的相邻顶点都可以通过链表快速获取，因此访问每个顶点的相邻顶点的时间复杂度为O(1)。总共有V个顶点，所以访问所有顶点的相邻顶点的时间复杂度为O(V)。

此外，对于每个顶点，我们需要判断其是否已经被访问过，这可以通过一个布尔数组来实现。初始化布尔数组需要O(V)的时间复杂度。在遍历过程中，每个顶点最多被访问一次，因此判断是否已经访问过的时间复杂度为O(1)。总共有V个顶点，所以判断所有顶点是否已经访问过的时间复杂度为O(V)。

综上所述，邻接表的深度优先遍历的时间复杂度为O(V+E)。

设N个顶点E条边的图用邻接表存储，则求每个顶点入度的时间复杂度为：

如果使用邻接表存储图，则可以采用统计每个顶点在所有邻接表中出现的次数的方法来计算每个顶点的入度。具体地，可以遍历邻接表中的所有边，对于每条边的终点，将其对应顶点的入度加1。由此，对于图中的每个顶点，都需要遍历其所有的邻接表，因此时间复杂度为O(E)，其中E为边的数量。

需要注意的是，在有向图中，每个顶点的出度和入度之和等于该顶点的度数，因此也可以统计每个顶点的度数来求出每个顶点的入度。但是在无向图中，每个顶点的度数等于其相邻顶点的数量，因此不能使用此方法来计算入度。