深度优先搜索算法（DFS）

深度优先搜索算法是一种用于遍历或搜索树或图的算法。它沿着树的深度尽可能远的搜索树的分支，直到这条路径上的所有节点都被访问过，然后返回到前一个节点。DFS 使用堆栈来实现，其时间复杂度和空间复杂度如下：

• 时间复杂度：
  • 最坏情况下，时间复杂度为 O(V + E)，其中 V 是顶点的数量，E 是边的数量。
  • 最好情况下，时间复杂度为 O(V)。
• 空间复杂度：
  • 最坏情况下，空间复杂度为 O(V)，其中 V 是顶点的数量。
  • 最好情况下，空间复杂度为 O(log(V))。

示例

public void dfs(int v, boolean[] visited, List<Integer>[] graph) {
    visited[v] = true;
    System.out.print(v + " ");
    for (int u : graph[v]) {
        if (!visited[u]) {
            dfs(u, visited, graph);
        }
    }
}