深度优先搜索-从顶点i出发深度搜索

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。在从一个顶点开始的情况下，深度优先搜索会首先访问该顶点，然后递归地访问该顶点的所有未访问过的邻居，并对每个邻居进行同样的操作，直到所有可达的顶点都被访问为止。

从顶点i出发的深度搜索过程可以简述为：

1. 首先标记顶点i为已访问。
2. 对于顶点i的每个未访问过的邻居v，递归地执行从v出发的深度搜索过程。
3. 深度搜索过程会一直递归下去，直到所有可达的顶点都被访问过为止。

深度优先搜索可以用来解决许多问题，比如寻找图中的连通分量、判断图是否有环等。

相关问题

Java 邻接表G中顶点v出发深度优先遍历

以下是 Java 邻接表中顶点v出发的深度优先遍历的代码实现：

public void DFS(int v, boolean[] visited) {
    // 标记当前顶点为已访问
    visited[v] = true;
    System.out.print(v + " ");

    // 遍历邻接表中与当前顶点相邻的未访问顶点
    for (int i = 0; i < adjList.get(v).size(); i++) {
        int u = adjList.get(v).get(i);
        if (!visited[u]) {
            DFS(u, visited);
        }
    }
}

其中，`v`表示起始顶点，`visited`数组表示每个顶点的访问状态（已访问为 true，未访问为 false）。首先将起始顶点 `v` 标记为已访问，并输出其值。然后遍历邻接表中与 `v` 相邻的所有未访问顶点，对每个未访问顶点递归调用 `DFS` 方法，直到所有顶点都被访问过为止。

Java 邻接表G中顶点v出发深度优先遍历并输出

好的，以下是 Java 邻接表 G 中顶点 v 出发的深度优先遍历代码：

import java.util.LinkedList;

public class Graph {
    private int V; // 顶点个数
    private LinkedList<Integer>[] adj; // 邻接表

    @SuppressWarnings("unchecked")
    public Graph(int V) {
        this.V = V;
        adj = new LinkedList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    // 添加一条边
    public void addEdge(int u, int v) {
        adj[u].add(v);
    }

    // 深度优先遍历
    public void DFS(int v) {
        boolean[] visited = new boolean[V];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int i : adj[v]) {
            if (!visited[i]) {
                DFSUtil(i, visited);
            }
        }
    }
}

在上面的代码中，我们定义了一个 `Graph` 类，其中：

- `V` 表示图中顶点的个数；
- `adj` 是一个邻接表，用于存储图中每个顶点的邻居；
- `addEdge` 方法用于向邻接表中添加一条边；
- `DFS` 方法是对外暴露的方法，用于从顶点 `v` 开始进行深度优先遍历；
- `DFSUtil` 方法是实际执行深度优先遍历的方法，其中 `visited` 数组用于标记每个顶点是否被访问过。

你可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("深度优先遍历结果:");
        g.DFS(2);
    }
}

输出结果为：

深度优先遍历结果:
2 0 1 3