图的深度优先遍历算法

深度优先遍历（Depth-First Search，DFS）是一种经典的图遍历算法，其基本思想是从图的某个顶点开始，沿着一条尽可能深的路径搜索，直到该路径不能继续为止，然后返回到最近的已经访问过的节点，继续尝试下一条路径，直到所有的顶点都被访问过为止。

DFS可以用递归或栈来实现。具体来说，以递归实现为例，其实现流程如下：

1. 从某个顶点开始遍历，将该顶点标记为已访问。

2. 对于该顶点的每个未访问过的邻居顶点，以递归的方式继续遍历。

3. 当所有邻居顶点都被访问过后，返回上一个顶点，继续尝试访问其它未访问过的邻居顶点。

4. 如果所有顶点都被访问过，则算法结束。

以下是DFS的伪代码实现：

void DFS(int v) {
    visited[v] = true; // 标记v为已访问
    for (auto w : adj[v]) {
        if (!visited[w]) { // 如果w未被访问过
            DFS(w); // 以w为起点继续遍历
        }
    }
}

其中，visited数组记录每个顶点是否被访问过，adj[v]表示与顶点v相邻的所有顶点。

需要注意的是，在实际应用中，可能需要处理一些特殊情况，例如图不连通或者存在环等情况，这些都需要在算法中进行相应的处理。同时，还需要注意DFS可能会陷入死循环，因此需要合理设置遍历的终止条件，以确保算法能够正确地结束。

图的深度优先遍历算法可以使用递归或者栈来实现。下面是使用递归实现的算法步骤：

1. 从起点开始遍历，将起点标记为已访问。

2. 访问起点的邻居节点，选择一个未被访问过的邻居节点，递归调用深度优先遍历算法，将该节点作为起点开始遍历。

3. 如果当前节点没有未被访问的邻居节点，退回到上一层递归调用，继续遍历上一层节点的未被访问的邻居节点。

4. 重复步骤2-3，直到图中所有节点都被访问过。

需要注意的是，在使用递归实现深度优先遍历时，需要注意避免重复访问节点。可以使用一个数组或者哈希表来记录每个节点是否被访问过。

下面是一个使用递归实现的深度优先遍历的示例代码：

#include <iostream>
#include <vector>

using namespace std;

// 递归遍历
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    visited[node] = true;  // 标记当前节点已访问
    cout << node << " ";   // 输出节点值

    // 遍历当前节点的所有邻居节点
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {  // 如果邻居节点未被访问，则递归访问
            dfs(graph, visited, neighbor);
        }
    }
}

// 深度优先遍历
void depthFirstSearch(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);  // 记录每个节点是否已访问
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {  // 对于未被访问的节点，以其为起点递归遍历整个图
            dfs(graph, visited, i);
        }
    }
}

int main() {
    // 以邻接表形式存储图结构
    vector<vector<int>> graph = {{1, 2}, {0, 3}, {0, 3}, {1, 2, 4}, {3}};
    depthFirstSearch(graph);  // 0 1 3 2 4

    return 0;
}

深度优先遍历的时间复杂度为 O(|V|+|E|)，其中 |V| 表示图中顶点的数量，|E| 表示边的数量。这是因为深度优先遍历需要访问所有的顶点和边，所以时间复杂度和图的规模有关。

需要注意的是，在稠密图中，即边数接近于顶点数平方的情况下，深度优先遍历的时间复杂度会接近于 O(|V|^2)；而在稀疏图中，即边数远小于顶点数平方的情况下，深度优先遍历的时间复杂度会接近于 O(|V|+|E|)。

另外，深度优先遍历的空间复杂度也和图的规模有关，主要是递归栈的空间占用。在最坏情况下，即图是一个连通的、深度为 h 的树时，递归栈的最大深度为 h，空间复杂度为 O(h)。

下面让我们来用数据图示演示一下深度优先遍历的过程。

   1---2
   |  /|
   | / |
   |/  |
   3---4---5

我们以1为起点进行深度优先遍历，过程如下：

1. 从节点1开始遍历，首先访问节点1，并将其标记为已访问。

2. 沿着未被访问过的边，访问与节点1相邻的节点2。

3. 继续沿着未被访问过的边，访问与节点2相邻的节点3。

4. 继续沿着未被访问过的边，访问与节点3相邻的节点4。

5. 继续沿着未被访问过的边，访问与节点4相邻的节点5。

6. 由于节点5没有与之相邻的未被访问过的节点，因此回溯到节点4，寻找其他未被访问过的相邻节点。

7. 由于节点4的相邻节点2已经被访问过了，因此回溯到节点3，寻找其他未被访问过的相邻节点。

8. 由于节点3的相邻节点1和4都已经被访问过了，因此回溯到节点2，寻找其他未被访问过的相邻节点。

9. 由于节点2的相邻节点1和3都已经被访问过了，因此回溯到节点1，寻找其他未被访问过的相邻节点。

10. 由于节点1没有与之相邻的未被访问过的节点，因此遍历结束。

因此，深度优先遍历的遍历顺序为：1 -> 2 -> 3 -> 4 -> 5。