数据结构与算法之深度优先算法详解

深度优先算法（Depth First Search，DFS）是一种常见的图形算法，它是一种用于遍历或搜索树或图的算法。在深度优先搜索中，我们首先探索一个子树的深度，然后再回溯到父节点，接着探索另一个子树的深度，直至搜索结束。

深度优先算法的基本思想是沿着树的深度遍历树的节点。深度优先算法的工作原理类似于树的前序遍历，即首先访问根节点，然后依次访问该节点的子节点。

深度优先算法可以用递归实现，也可以使用栈来实现。下面我们详细介绍这两种实现方式。

1. 递归实现深度优先算法

下面是使用递归实现深度优先算法的示例代码：

void dfs(int node, vector &visited, vector> &graph) {// 标记节点node已被访问visited[node] = true;// 访问节点nodecout << node << " ";// 遍历node的所有邻居节点for (int i = 0; i < graph[node].size(); i++) {int neighbor = graph[node][i];// 如果邻居节点未被访问，则递归访问它if (!visited[neighbor]) {dfs(neighbor, visited, graph);}}
}

在这个示例中，我们首先定义一个函数dfs，它接收三个参数，分别是当前节点node、表示节点是否被访问的visited向量以及描绘图的邻接矩阵graph。在函数内部，我们首先将当前节点标记为已访问，并输出该节点的编号。然后我们遍历该节点的所有邻居节点，如果邻居节点未被访问，则递归地访问它。递归的终止条件是遍历完所有节点。

1. 栈实现深度优先算法

下面是使用栈实现深度优先算法的示例代码：

void dfs(int node, vector &visited, vector> &graph) {stack stk;// 将起始节点入栈stk.push(node);while (!stk.empty()) {// 取出栈顶元素int cur = stk.top();stk.pop();// 如果当前节点未被访问，则访问它if (!visited[cur]) {visited[cur] = true;cout << cur << " ";// 将当前节点的邻居节点入栈for (int i = graph[cur].size() - 1; i >= 0; i--) {int neighbor = graph[cur][i];if (!visited[neighbor]) {stk.push(neighbor);}}}}
}

在这个示例中，我们首先定义一个函数dfs，它接收三个参数，分别是当前节点node、表示节点是否被访问的visited向量以及描绘图的邻接矩阵graph。在函数内部，我们创建一个栈，并将初始节点node入栈。在栈未空之前，我们重复执行以下步骤：

• 取出栈顶元素
• 如果当前节点未被访问，则将其标记为已访问，并输出该节点的编号
• 遍历该节点的所有邻居节点，如果邻居节点未被访问，则将其入栈

在程序的最后，我们完成了整个深度优先遍历。

深度优先算法的时间复杂度为$O(V+E)$，其中$V$是图的节点数量，$E$是图的边数量。因为在遍历每个节点和边的时候，每个节点和边都会被访问一次。另外，深度优先算法的空间复杂度为$O(V)$，其中$V$是图的节点数量，因为需要存储每个节点的访问状态。