什么是图的遍历？
----------------------

图的遍历是指从图中的某个顶点出发，按照一定的规则依次访问图中的所有顶点，且每个顶点只被访问一次的过程。可以理解为是对图中顶点的一种全面的访问。

图的遍历分为深度优先搜索（DFS）和广度优先搜索（BFS）两种方式。深度优先搜索是先访问某个顶点的所有邻接顶点，再递归地访问邻接顶点的邻接顶点，直到访问完所有可达的顶点。广度优先搜索则是先访问某个顶点的所有邻接顶点，再按距离由近及远的顺序依次访问邻接顶点的邻接顶点，直到访问完所有可达的顶点。

深度优先搜索的实现
------------------

深度优先搜索可以使用递归或栈来实现。下面是使用递归实现深度优先搜索的代码示例：

public void dfs(int v, boolean[] visited) {
    visited[v] = true;  // 标记顶点v为已访问
    System.out.print(v + " ");
  
    // 递归访问顶点v的所有邻接顶点
    for (int i : adj[v]) {
        if (!visited[i]) {
            dfs(i, visited);
        }
    }
}
Java

1. 首先，创建一个大小为顶点数的布尔数组 visited，标记所有顶点为未访问状态。
2. 调用 dfs 方法，传入起始顶点和 visited 数组。
3. 在 dfs 方法内部，首先将当前顶点标记为已访问，并输出该顶点。
4. 遍历当前顶点的所有邻接顶点，如果邻接顶点未被访问过，则递归调用 dfs 方法，传入邻接顶点和 visited 数组。

广度优先搜索的实现
------------------

广度优先搜索可以使用队列来实现。下面是使用队列实现广度优先搜索的代码示例：

public void bfs(int s) {
    boolean[] visited = new boolean[v];  // 标记顶点是否已访问
    Queue queue = new LinkedList<>();  // 创建一个队列保存待访问的顶点
  
    visited[s] = true;
    queue.offer(s);  // 将起始顶点入队
  
    while (!queue.isEmpty()) {
        int v = queue.poll();  // 将队首顶点出队并访问
        System.out.print(v + " ");
  
        // 遍历顶点v的所有邻接顶点
        for (int i : adj[v]) {
            if (!visited[i]) {
                visited[i] = true;
                queue.offer(i);  // 将未访问的顶点入队
            }
        }
    }
}
Java

1. 首先，创建一个大小为顶点数的布尔数组 visited，标记所有顶点为未访问状态。
2. 创建一个队列，用于保存待访问的顶点。
3. 将起始顶点标记为已访问，并将其入队。
4. 使用 while 循环，直到队列为空。
5. 在循环内部，将队首顶点出队，并访问之。
6. 遍历当前顶点的所有邻接顶点，如果邻接顶点未被访问过，则将其标记为已访问并入队。

两种遍历方式的比较
------------------

深度优先搜索和广度优先搜索有各自的应用场景。深度优先搜索一般用于查找路径和连通性等问题，它能够快速到达最深层次的顶点。广度优先搜索一般用于查找最短路径和路径的层次等问题，它能够逐层扩展，从起点到终点的路径经过的边数最少。

总结起来，图的遍历是通过一定的策略，按照一定的顺序访问图中的所有顶点。深度优先搜索和广度优先搜索是两种常用的图遍历方式，它们分别通过递归和队列来实现。深度优先搜索适用于查找路径和连通性等问题，广度优先搜索适用于查找最短路径和路径的层次等问题。