dfs遍历图可以通过递归或栈实现

深度优先搜索（DFS）是一种在数据结构中对数据进行遍历的算法，其思想是先尽可能地往深里面走，直到无法再深入为止，然后再回溯到上一个节点继续搜索。在遍历图的时候，可以通过递归或者栈来实现。本文将从多个角度分析DFS遍历图的递归和栈实现。

一、递归实现DFS遍历图

递归是指函数在运行过程中直接或间接地调用自己。递归实现DFS遍历图的基本思路是从某个顶点开始，首先访问这个顶点，然后对于这个顶点的每一个未被访问过的邻接点，将其递归的进行访问。递归实现DFS遍历图的代码实现如下：

void DFS(int v) {

visited[v] = true;

for (int i = 0; i < graph[v].size(); i++) {

int next = graph[v][i];

if (!visited[next]) {

DFS(next);

}

}

}

这个函数的参数v表示当前的顶点，visited数组表示每个顶点是否被访问过，graph表示图的邻接表。在函数内，首先将当前顶点v标记为已经访问过，然后对于每一个未被访问过的邻接点，将其递归的进行访问。这个函数的时间复杂度是O(V+E)，其中V表示顶点的数量，E表示边的数量。

二、栈实现DFS遍历图

栈是一种后进先出（LIFO）的数据结构，在遍历图的时候，可以通过维护一个栈来实现DFS。其实现思路是从某一个顶点开始，将其加入栈中，然后从栈中弹出一个元素，访问它的邻接点，并将未被访问的邻接点加入栈中。重复这个过程直到栈为空。栈实现DFS遍历图的代码实现如下：

void DFS(int start) {

stack s;

bool visited[MAXV] = { false };

s.push(start);

visited[start] = true;

while (!s.empty()) {

int v = s.top();

s.pop();

for (int i = 0; i < graph[v].size(); i++) {

int next = graph[v][i];

if (!visited[next]) {

visited[next] = true;

s.push(next);

}

}

}

}

这个函数的参数start表示起始节点，visited数组表示每个顶点是否被访问过，graph表示图的邻接表。在函数内，首先创建一个空栈，将起始节点加入栈中，并将其标记为已经访问过。然后重复从栈中弹出一个元素，访问它的邻接点，并将未被访问的邻接点加入栈中的操作，直到栈为空。这个函数的时间复杂度是O(V+E)，其中V表示顶点的数量，E表示边的数量。

三、递归实现和栈实现的比较

在实现DFS遍历图的时候，递归实现和栈实现是两种常用的方式。它们各有优缺点：

1.递归实现的优点是代码简洁易懂，可以更好地理解DFS算法的思想。递归过程中，程序利用系统的调用栈来维护DFS搜索的深度，代码的可读性和易用性较强。

2.递归实现的缺点是存在栈的空间开销。若图的结点数量和结构发生改变，递归算法的空间开销也会发生变化。

3.栈实现的优点是可以更好地控制DFS的深度和空间复杂度，避免因递归过深产生栈溢出的错误。

4.栈实现的缺点是代码实现复杂，容易出错，且相比于递归实现来说，代码难以理解。

综上所述，递归实现和栈实现各有其优点和缺点，可以根据实际情况进行选择。