算法7-4,7-5：图的遍历——深度优先搜索

### 回答1：
算法7-4：深度优先搜索

1. 从起点开始，将其标记为已访问。
2. 对于起点的每个未访问的邻居，递归地执行步骤1-2。
3. 重复步骤2，直到没有未访问的邻居。

算法7-5：深度优先搜索（非递归）

1. 从起点开始，将其标记为已访问，并将其压入栈中。
2. 当栈不为空时，弹出栈顶元素，并对其每个未访问的邻居执行步骤1-2，并将其标记为已访问并压入栈中。
3. 重复步骤2，直到栈为空。

### 回答2：
一、定义

深度优先搜索（Depth First Search，DFS）是图论中的基本算法，是从图的某个节点出发，访问这个节点，然后依次访问这个节点的每个未被访问的邻居节点，直至遍历完整个图。

二、实现

深度优先搜索可以通过递归或栈的方式实现。递归实现简单，但难以控制递归深度，容易发生栈溢出。栈的实现需要手动模拟栈，但可以灵活控制深度，避免栈溢出。

递归实现：

1.从某个节点v开始遍历。

2.标记该节点v为已访问。

3.对于v的每个未被访问的邻居节点w，递归访问w。

栈实现：

1.从某个节点v开始遍历。

2.将v入栈，并标记v为已访问。

3.当栈非空时循环执行以下步骤：弹出栈顶节点u，对于u的每个未被访问的邻居节点w，将w入栈并标记w为已访问。

三、应用

深度优先搜索可以用来判断图是否连通，可用于求解最小生成树、拓扑排序、连通分量等问题。

由于深度优先搜索需要存储所有已访问节点的路径，所以针对大规模图的遍历可能导致空间复杂度较高。

四、算法7-4，7-5代码分析

算法7-4：

算法7-4是对图的深度优先遍历的递归实现。首先遍历该节点，并标记为已访问，然后将该节点的所有邻居节点都遍历一遍。如果邻居节点未被访问，则对该节点进行递归调用进行遍历。

具体思路：

1.定义全局vis数组，用于记录节点是否已被访问。

2.定义一个函数dfs(u)，对节点u进行深度优先遍历。遍历完u的所有邻居节点后，会回溯到该节点u的上一个节点。

3.主函数遍历所有节点，对未被访问的节点进行深度优先遍历。

算法7-5：

算法7-5是对图的深度优先遍历的栈实现。使用了一个栈来存储待访问节点。首先将初始节点加入栈中，并标记为已访问，然后循环遍历栈中的节点，直至栈为空。

具体思路：

1.定义全局vis数组，用于记录节点是否已被访问。

2.定义一个函数dfs(u)，对节点u进行深度优先遍历。遍历完u的所有邻居节点后，会回溯到该节点u的上一个节点。

3.主函数遍历所有节点，对未被访问的节点进行深度优先遍历。在遍历到未被访问的节点时，加入栈中并标记为已访问，然后循环遍历栈中的节点，直至栈为空。

### 回答3：
算法7-4，7-5是关于图的遍历中的深度优先搜索（DFS），主要是用来搜索和遍历图中所有的节点和边的算法。

深度优先搜索的核心思想是：从一个未访问的节点开始，深度优先遍历到最深处，然后回溯到上一个节点，再从上一个未遍历节点开始继续深度优先遍历。在具体实现过程中，我们可以使用递归或栈来实现深度优先搜索算法。

深度优先搜索算法在图的遍历、搜索、路径查找等方面有着广泛的应用，如迷宫问题、拓扑排序、关键路径等。

在算法7-4中，我们给出了使用递归实现深度优先搜索的伪代码：

void DFS(int u) {
    vis[u] = true; // 标记已经访问过
    // 遍历所有邻接节点
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i]; // 取出邻接节点
        if (!vis[v]) {
            DFS(v); // 继续遍历
        }
    }
}

而在算法7-5中，我们使用栈来实现深度优先搜索，具体实现过程如下：

void DFS(int u) {
    stack<int> s; // 定义一个栈
    s.push(u); // 将起始节点放入栈中
    vis[u] = true; // 标记已经访问过

    while (!s.empty()) {
        int v = s.top(); // 取出栈顶节点
        s.pop(); // 将该节点出栈
        // 遍历所有邻接节点
        for (int i = 0; i < G[v].size(); i++) {
            int w = G[v][i]; // 取出邻接节点
            if (!vis[w]) {
                s.push(w); // 将未访问节点放入栈中
                vis[w] = true; // 标记已访问
            }
        }
    }
}

总之，深度优先搜索算法是一种基本的图遍历算法，其核心思想和实现方法都比较简单，但是能够灵活应用在众多图相关的算法问题中。