图的遍历中的深度优先遍历方法总结

图的遍历中的深度优先遍历方法总结一、深度优先遍历（DFS）概述

深度优先遍历是一种用于遍历或搜索树或图的算法。该算法从根节点（或任意起始节点）开始，尽可能深入地探索每条边，直到无法继续前进，然后回溯到上一个节点，继续探索其他未访问的边。深度优先遍历主要有三种实现方式：递归、栈模拟和邻接表迭代。

二、深度优先遍历的实现方法

（一）递归实现

递归是实现深度优先遍历最直观的方法。算法从起始节点出发，递归访问每个未访问的邻接节点，直到所有节点都被访问。

1.算法步骤：

(1)标记当前节点为已访问。

(2)遍历当前节点的所有邻接节点。

(3)如果邻接节点未被访问，则递归调用深度优先遍历函数。

(4)如果所有邻接节点已访问，则回溯到上一个节点。

2.示例代码（伪代码）：

```

voidDFS(Nodenode):

if(node==null)return;

mark(nodeasvisited);

for(Nodeneighborinnode.neighbors):

if(!neighbor.visited):

DFS(neighbor);

```

（二）栈模拟实现

对于无法使用递归的情况（如深度过深导致栈溢出），可以使用栈来模拟递归过程。

1.算法步骤：

(1)初始化一个空栈，将起始节点入栈并标记为已访问。

(2)当栈不为空时：

a.出栈一个节点，记录或处理该节点。

b.遍历该节点的所有邻接节点。

c.如果邻接节点未被访问，则将其入栈并标记为已访问。

2.示例代码（伪代码）：

```

voidDFS(Nodestart):

Stackstack=newStack();

stack.push(start);

mark(startasvisited);

while(!stack.isEmpty()):

Nodenode=stack.pop();

process(node);

for(Nodeneighborinnode.neighbors):

if(!neighbor.visited):

stack.push(neighbor);

mark(neighborasvisited);

```

（三）邻接表迭代实现

结合邻接表和栈的迭代实现，可以更高效地处理大型图结构。

1.算法步骤：

(1)初始化一个空栈和一个空集合记录已访问节点。

(2)将起始节点入栈并标记为已访问。

(3)当栈不为空时：

a.出栈一个节点，记录或处理该节点。

b.获取该节点的邻接节点列表，按顺序反转（优先访问未访问的节点）。

c.将所有未访问的邻接节点入栈并标记为已访问。

2.示例代码（伪代码）：

```

voidDFS(Nodestart):

Stackstack=newStack();

Setvisited=newSet();

stack.push(start);

mark(startasvisited);

while(!stack.isEmpty()):

Nodenode=stack.pop();

process(node);

Listneighbors=getNeighbors(node);

for(inti=neighbors.size()-1;i>=0;i--):

Nodeneighbor=neighbors[i];

if(!neighbor.visited):

stack.push(neighbor);

mark(neighborasvisited);

```

三、深度优先遍历的应用场景

1.图的连通性判断：通过深度优先遍历可以判断图是否连通。

2.拓扑排序：在有向无环图中，深度优先遍历可用于生成拓扑序列。

3.寻找路径或环：深度优先遍历可以用于检测图中是否存在特定路径或环。

4.子图搜索：在大型图中查找符合特定条件的子图结构。

四、深度优先遍历的优缺点

（一）优点

1.空间复杂度较低：递归实现只需O(h)栈空间（h为深度），迭代实现需O(V)空间记录访问状态。

2.易于实现：递归方式代码简洁直观。

3.适用于稀疏图：在边数较少的图中效率较高。

（二）缺点

1.可能陷入无限循环：在含有环的图中需额外标记访问状态。

2.深度限制：递归方式在深度过大的图中可能导致栈溢出。

3.时间复杂度：最坏情况下需访问所有节点和边（O(V+E)）。

五、总结

深度优先遍历是图算法中基础且重要的方法，通过递归或栈模拟可以实现。根据具体应用场景选择合适的方法，如递归适用于小型图，栈模拟适用于大型图或深度受限的情况。深度优先遍历在连通性判断、拓扑排序等领域有广泛应用，但需注意处理环和深度限制的问题。

一、深度优先遍历（DFS）概述

深度优先遍历（Depth-FirstSearch,DFS）是一种在树或图中进行搜索的算法策略。其核心思想是优先向深处探索，尽可能沿着一条路径访问节点的邻接节点，直到无法继续前进（即当前节点没有未访问的邻接节点），然后回溯到上一个节点，继续探索该节点的其他未访问邻接节点。这种策略如同“深入洞穴探险”，一直走到最深处，如果走不通就退回一步，尝试其他方向。

深度优先遍历主要有三种常见的实现方式：递归实现、使用显式栈的迭代实现以及基于邻接表的迭代实现。每种方式都有其适用的场景和优缺点。理解这些实现方式有助于在实际问题中灵活选择最合适的算法。

二、深度优先遍历的实现方法

（一）递归实现

递归是实现深度优先遍历最直接、最自然的方法。算法的设计思路清晰：访问一个节点，然后对其每个未访问的邻接节点递归地进行同样的操作。

1.算法步骤详解：

(1)访问节点并标记：首先，处理当前节点（例如，打印节点信息、检查节点属性等）。然后，立即将该节点标记为已访问，以避免重复访问和无限循环。标记可以通过设置节点的某个布尔属性（如`visited=true`）或将其加入一个已访问集合中来实现。

(2)遍历邻接节点：获取当前节点的所有邻接节点（即与当前节点直接相连的节点）。这通常通过图的数据结构（如邻接矩阵或邻接表）来获取。

(3)递归访问未访问的邻接节点：对于当前节点的每一个邻接节点，检查该邻接节点是否已被访问。如果尚未访问，则对该邻接节点递归地执行步骤(1)和(2)。这意味着控制权会转移到被访问的邻接节点，继续深入探索。

(4)回溯：当当前节点的所有未访问邻接节点都已被递归访问后，递归调用结束，控制权返回到上一个调用DFS的节点。这个过程称为回溯。在回溯时，当前节点已经完成了对其所有邻接节点的探索。回溯机制是递归调用栈自动完成的。

2.示例代码（伪代码-递归）：

```

voidrecursiveDFS(Nodecurrent,Setvisited):

if(current==null||visited.contains(current)):

return;//基本情况：节点为空或已访问

//(1)访问节点并标记

process(current);//处理当前节点，如打印或存储

visited.add(current);

//(2)遍历邻接节点

Listneighbors=getNeighbors(current);//获取当前节点的所有未定义邻接节点列表

//(3)递归访问未访问的邻接节点

for(Nodeneighborinneighbors):

if(!visited.contains(neighbor)):

recursiveDFS(neighbor,visited);

//(4)回溯已完成，递归调用结束，控制权返回到调用者

```

在调用时，需要传入一个空的已访问集合和一个起始节点：

```

Setvisited=newHashSet();

recursiveDFS(startNode,visited);

```

（二）栈模拟实现

当系统栈深度有限（例如，在处理非常深的递归时可能发生栈溢出）或需要显式控制遍历过程时，可以使用显式的栈来模拟递归的深度优先遍历。

1.算法步骤详解：

(1)初始化：创建一个空栈和一个空集合用于记录已访问节点。将起始节点入栈，并立即将其标记为已访问（因为入栈操作本身就代表了“访问”的开始）。

(2)循环处理栈非空：当栈不为空时，执行以下操作：

a.出栈节点：从栈顶弹出一个节点，这是当前要处理（访问）的节点。记为`current`。

b.处理节点：对`current`节点进行处理（例如，打印或存储其信息）。

c.获取并处理邻接节点：

i.获取`current`节点的所有邻接节点列表。

ii.遍历这些邻接节点。对于每一个邻接节点`neighbor`：

-检查`neighbor`是否已被访问。如果未访问：

-将`neighbor`节点入栈。

-将`neighbor`标记为已访问。

-如果`neighbor`已访问，则忽略。

(3)结束条件：当栈为空时，所有可从起始节点通过路径到达的节点都已被访问，遍历结束。

2.示例代码（伪代码-栈模拟）：

```

voiditerativeDFS(Nodestart):

if(start==null):

return;

Stackstack=newStack();

Setvisited=newHashSet();

//(1)初始化：起始节点入栈并标记

stack.push(start);

visited.add(start);

//(2)循环处理栈非空

while(!stack.isEmpty()):

//(2a)出栈节点

Nodecurrent=stack.pop();

process(current);//处理当前节点

//(2b)获取并处理邻接节点（按特定顺序，如逆序以优先访问未访问的）

Listneighbors=getNeighbors(current);

//例如，按列表原始顺序的反序处理邻接节点：

for(inti=neighbors.size()-1;i>=0;i--):

Nodeneighbor=neighbors[i];

if(!visited.contains(neighbor)):

stack.push(neighbor);

visited.add(neighbor);

//(3)结束条件（自然在循环结束时达成）

```

（三）邻接表迭代实现

结合邻接表（一种高效的图表示方法）和栈的迭代实现，可以清晰地管理节点的访问状态和遍历顺序，特别适用于需要显式控制或处理特定邻接节点顺序的场景。

1.算法步骤详解：

(1)初始化：创建一个空栈用于模拟递归调用栈，创建一个空集合用于记录已访问节点。将起始节点入栈并标记为已访问。

(2)循环处理栈非空：当栈不为空时，执行以下操作：

a.出栈节点：从栈顶弹出一个节点，记为`current`。

b.处理节点：对`current`节点进行处理。

c.准备访问邻接节点：获取`current`节点的所有邻接节点列表。

d.反向遍历邻接节点：为了确保在将邻接节点入栈时，它们是按照期望的顺序（例如，先访问编号较小的邻接节点，或者与邻接表存储顺序一致）被处理的，通常需要将邻接节点列表进行反转。然后，遍历反转后的邻接节点列表：

i.对于每一个邻接节点`neighbor`：

-检查`neighbor`是否已被访问。如果未访问：

-将`neighbor`节点入栈。

-将`neighbor`标记为已访问。

-如果`neighbor`已访问，则忽略。

(3)结束条件：当栈为空时，遍历结束。

2.示例代码（伪代码-邻接表迭代）：

```

voidadjacencyListDFS(Nodestart):

if(start==null):

return;

Stackstack=newStack();

Setvisited=newHashSet();

//(1)初始化：起始节点入栈并标记

stack.push(start);

visited.add(start);

//(2)循环处理栈非空

while(!stack.isEmpty()):

//(2a)出栈节点

Nodecurrent=stack.pop();

process(current);//处理当前节点

//(2b)获取当前节点的邻接节点列表

Listneighbors=getNeighbors(current);

//(2c)反向遍历邻接节点列表

for(inti=neighbors.size()-1;i>=0;i--):

Nodeneighbor=neighbors[i];

if(!visited.contains(neighbor)):

stack.push(neighbor);

visited.add(neighbor);

//(3)结束条件（自然在循环结束时达成）

```

三、深度优先遍历的应用场景

深度优先遍历因其探索路径的特性，在多种场景下非常有用。以下是一些典型的应用：

1.连通性判断：

(1)判断无向图是否连通：从任意一个节点开始进行深度优先遍历。遍历结束后，如果所有节点都被访问过，则图是连通的；否则，图是不连通的（至少存在两个不连通的分量）。

(2)查找无向图的连通分量：从未访问的节点开始进行深度优先遍历，遍历过程中访问到的所有节点属于同一个连通分量。对每个未访问的节点重复此过程，即可找到所有连通分量。

2.路径寻找：

(1)查找简单路径：虽然广度优先搜索（BFS）通常能找到最短路径，但DFS可以用来查找是否存在一条从起点到终点的路径，尤其是在不关心路径长度的情况下。

(2)检测环：在遍历过程中，如果遇到一个节点，其某个邻接节点已经被访问过（且不是直接父节点），则图中存在环。

3.拓扑排序：

(1)在有向无环图（DAG）中：拓扑排序是一种将图中所有节点排成一个线性序列，使得对于每一条有向边(u,v)，节点u在序列中出现在节点v之前。深度优先遍历可以用来实现拓扑排序。通常采用“逆波兰表示法”（Post-order）或“Kahn算法”（基于入度）两种基于DFS/BFS的方法。DFS的实现方式是：对每个节点进行DFS，当DFS结束时（即该节点是当前连通分量中的叶子节点或已处理完所有出边），将其加入一个栈中。最终栈中节点的顺序即为拓扑排序的结果。

4.子图搜索：

(1)寻找满足特定条件的子结构：例如，在大型网络中查找所有包含特定节点配置的子图（如特定的环结构、树结构等）。

5.游戏和谜题求解：

(1)回溯法：DFS是回溯法的基础。在解谜题（如数独、八数码）或游戏（如迷宫求解、棋盘路径规划）时，DFS可以用来尝试所有可能的路径，直到找到解决方案或证明无解。

四、深度优先遍历的优缺点

（一）优点

1.空间复杂度相对较低：

(1)递归实现：空间复杂度为O(h)，其中h是递归的深度。对于稀疏图或浅层递归，空间效率很高。

(2)迭代实现（栈模拟）：空间复杂度为O(V)，其中V是图中节点的数量。在最坏情况下（例如，树状结构且从根节点出发），栈的大小也接近V。对于连通图，通常栈大小与节点数或边数相关。

2.实现相对简单直观：尤其是递归实现，代码通常更简洁，易于理解和编写。

3.适用于稀疏图：当图中的边数远小于节点数的平方（即稀疏图）时，DFS通常比需要存储所有边或所有邻接关系的算法（如某些BFS变体）更节省空间。

4.能快速探索深层结构：如果目标节点位于图的深处，DFS可能会更快地找到它，因为它不断深入。

（二）缺点

1.可能陷入无限循环：

(1)有向图中的环：如果图中含有环，且在遍历过程中没有正确地标记节点为已访问，DFS可能会无限循环访问环中的节点。

(2)解决方案：必须确保在访问每个节点时都进行标记，并且在递归调用或栈入栈操作前检查节点是否已访问。

2.深度限制与栈溢出：

(1)递归实现：当图非常深（即递归深度很大）时，系统调用栈可能会溢出。这是递归实现DFS的主要局限性之一。

(2)解决方案：对于深度非常大的图，应优先使用栈模拟的迭代实现。

3.不保证找到最短路径：DFS不保证找到从起点到终点的最短路径（除非图是加权无环图且所有边权重相同，此时最短路径与DFS遍历顺序一致）。它只是探索一条任意深的路径。

4.可能错过最优解：在搜索问题中，DFS可能会过早地进入一条看似有希望的路径，并消耗大量时间，而最优解可能存在于其他未探索的分支中。这不如广度优先搜索（BFS）全面。

5.对大规模数据可能效率不高：对于需要快速找到所有解或最短解的问题，DFS可能会探索大量不必要的节点，导致效率低下。

五、总结

深度优先遍历（DFS）是一种强大而灵活的图搜索算法，通过递归或显式栈的迭代方式实现。递归实现简洁直观，但易受栈深度限制；栈模拟的迭代实现更为通用，能处理更深的图，但代码稍显复杂。基于邻接表的迭代实现则提供了更清晰的控制邻接节点访问顺序的方式。

DFS的核心在于“深入探索”和“回溯”。它在连通性判断、环检测、拓扑排序、子图搜索以及作为回溯法基础等众多领域有着广泛应用。

选择DFS还是其他图搜索算法（如BFS）取决于具体问题的需求：需要最短路径或全面搜索时，BFS通常更优；需要空间效率或快速探索深层结构时，DFS可能是更好的选择。同时，使用DFS时必须注意处理环（通过标记已访问节点）和深度限制（优先考虑迭代实现或限制递归深度）的问题。理解并掌握DFS的各种实现方法和应用场景，对于解决复杂的图结构问题至关重要。

一、深度优先遍历（DFS）概述

深度优先遍历是一种用于遍历或搜索树或图的算法。该算法从根节点（或任意起始节点）开始，尽可能深入地探索每条边，直到无法继续前进，然后回溯到上一个节点，继续探索其他未访问的边。深度优先遍历主要有三种实现方式：递归、栈模拟和邻接表迭代。

二、深度优先遍历的实现方法

（一）递归实现

递归是实现深度优先遍历最直观的方法。算法从起始节点出发，递归访问每个未访问的邻接节点，直到所有节点都被访问。

1.算法步骤：

(1)标记当前节点为已访问。

(2)遍历当前节点的所有邻接节点。

(3)如果邻接节点未被访问，则递归调用深度优先遍历函数。

(4)如果所有邻接节点已访问，则回溯到上一个节点。

2.示例代码（伪代码）：

```

voidDFS(Nodenode):

if(node==null)return;

mark(nodeasvisited);

for(Nodeneighborinnode.neighbors):

if(!neighbor.visited):

DFS(neighbor);

```

（二）栈模拟实现

对于无法使用递归的情况（如深度过深导致栈溢出），可以使用栈来模拟递归过程。

1.算法步骤：

(1)初始化一个空栈，将起始节点入栈并标记为已访问。

(2)当栈不为空时：

a.出栈一个节点，记录或处理该节点。

b.遍历该节点的所有邻接节点。

c.如果邻接节点未被访问，则将其入栈并标记为已访问。

2.示例代码（伪代码）：

```

voidDFS(Nodestart):

Stackstack=newStack();

stack.push(start);

mark(startasvisited);

while(!stack.isEmpty()):

Nodenode=stack.pop();

process(node);

for(Nodeneighborinnode.neighbors):

if(!neighbor.visited):

stack.push(neighbor);

mark(neighborasvisited);

```

（三）邻接表迭代实现

结合邻接表和栈的迭代实现，可以更高效地处理大型图结构。

1.算法步骤：

(1)初始化一个空栈和一个空集合记录已访问节点。

(2)将起始节点入栈并标记为已访问。

(3)当栈不为空时：

a.出栈一个节点，记录或处理该节点。

b.获取该节点的邻接节点列表，按顺序反转（优先访问未访问的节点）。

c.将所有未访问的邻接节点入栈并标记为已访问。

2.示例代码（伪代码）：

```

voidDFS(Nodestart):

Stackstack=newStack();

Setvisited=newSet();

stack.push(start);

mark(startasvisited);

while(!stack.isEmpty()):

Nodenode=stack.pop();

process(node);

Listneighbors=getNeighbors(node);

for(inti=neighbors.size()-1;i>=0;i--):

Nodeneighbor=neighbors[i];

if(!neighbor.visited):

stack.push(neighbor);

mark(neighborasvisited);

```

三、深度优先遍历的应用场景

1.图的连通性判断：通过深度优先遍历可以判断图是否连通。

2.拓扑排序：在有向无环图中，深度优先遍历可用于生成拓扑序列。

3.寻找路径或环：深度优先遍历可以用于检测图中是否存在特定路径或环。

4.子图搜索：在大型图中查找符合特定条件的子图结构。

四、深度优先遍历的优缺点

（一）优点

1.空间复杂度较低：递归实现只需O(h)栈空间（h为深度），迭代实现需O(V)空间记录访问状态。

2.易于实现：递归方式代码简洁直观。

3.适用于稀疏图：在边数较少的图中效率较高。

（二）缺点

1.可能陷入无限循环：在含有环的图中需额外标记访问状态。

2.深度限制：递归方式在深度过大的图中可能导致栈溢出。

3.时间复杂度：最坏情况下需访问所有节点和边（O(V+E)）。

五、总结

深度优先遍历是图算法中基础且重要的方法，通过递归或栈模拟可以实现。根据具体应用场景选择合适的方法，如递归适用于小型图，栈模拟适用于大型图或深度受限的情况。深度优先遍历在连通性判断、拓扑排序等领域有广泛应用，但需注意处理环和深度限制的问题。

一、深度优先遍历（DFS）概述

深度优先遍历（Depth-FirstSearch,DFS）是一种在树或图中进行搜索的算法策略。其核心思想是优先向深处探索，尽可能沿着一条路径访问节点的邻接节点，直到无法继续前进（即当前节点没有未访问的邻接节点），然后回溯到上一个节点，继续探索该节点的其他未访问邻接节点。这种策略如同“深入洞穴探险”，一直走到最深处，如果走不通就退回一步，尝试其他方向。

深度优先遍历主要有三种常见的实现方式：递归实现、使用显式栈的迭代实现以及基于邻接表的迭代实现。每种方式都有其适用的场景和优缺点。理解这些实现方式有助于在实际问题中灵活选择最合适的算法。

二、深度优先遍历的实现方法

（一）递归实现

递归是实现深度优先遍历最直接、最自然的方法。算法的设计思路清晰：访问一个节点，然后对其每个未访问的邻接节点递归地进行同样的操作。

1.算法步骤详解：

(1)访问节点并标记：首先，处理当前节点（例如，打印节点信息、检查节点属性等）。然后，立即将该节点标记为已访问，以避免重复访问和无限循环。标记可以通过设置节点的某个布尔属性（如`visited=true`）或将其加入一个已访问集合中来实现。

(2)遍历邻接节点：获取当前节点的所有邻接节点（即与当前节点直接相连的节点）。这通常通过图的数据结构（如邻接矩阵或邻接表）来获取。

(3)递归访问未访问的邻接节点：对于当前节点的每一个邻接节点，检查该邻接节点是否已被访问。如果尚未访问，则对该邻接节点递归地执行步骤(1)和(2)。这意味着控制权会转移到被访问的邻接节点，继续深入探索。

(4)回溯：当当前节点的所有未访问邻接节点都已被递归访问后，递归调用结束，控制权返回到上一个调用DFS的节点。这个过程称为回溯。在回溯时，当前节点已经完成了对其所有邻接节点的探索。回溯机制是递归调用栈自动完成的。

2.示例代码（伪代码-递归）：

```

voidrecursiveDFS(Nodecurrent,Setvisited):

if(current==null||visited.contains(current)):

return;//基本情况：节点为空或已访问

//(1)访问节点并标记

process(current);//处理当前节点，如打印或存储

visited.add(current);

//(2)遍历邻接节点

Listneighbors=getNeighbors(current);//获取当前节点的所有未定义邻接节点列表

//(3)递归访问未访问的邻接节点

for(Nodeneighborinneighbors):

if(!visited.contains(neighbor)):

recursiveDFS(neighbor,visited);

//(4)回溯已完成，递归调用结束，控制权返回到调用者

```

在调用时，需要传入一个空的已访问集合和一个起始节点：

```

Setvisited=newHashSet();

recursiveDFS(startNode,visited);

```

（二）栈模拟实现

当系统栈深度有限（例如，在处理非常深的递归时可能发生栈溢出）或需要显式控制遍历过程时，可以使用显式的栈来模拟递归的深度优先遍历。

1.算法步骤详解：

(1)初始化：创建一个空栈和一个空集合用于记录已访问节点。将起始节点入栈，并立即将其标记为已访问（因为入栈操作本身就代表了“访问”的开始）。

(2)循环处理栈非空：当栈不为空时，执行以下操作：

a.出栈节点：从栈顶弹出一个节点，这是当前要处理（访问）的节点。记为`current`。

b.处理节点：对`current`节点进行处理（例如，打印或存储其信息）。

c.获取并处理邻接节点：

i.获取`current`节点的所有邻接节点列表。

ii.遍历这些邻接节点。对于每一个邻接节点`neighbor`：

-检查`neighbor`是否已被访问。如果未访问：

-将`neighbor`节点入栈。

-将`neighbor`标记为已访问。

-如果`neighbor`已访问，则忽略。

(3)结束条件：当栈为空时，所有可从起始节点通过路径到达的节点都已被访问，遍历结束。

2.示例代码（伪代码-栈模拟）：

```

voiditerativeDFS(Nodestart):

if(start==null):

return;

Stackstack=newStack();

Setvisited=newHashSet();

//(1)初始化：起始节点入栈并标记

stack.push(start);

visited.add(start);

//(2)循环处理栈非空

while(!stack.isEmpty()):

//(2a)出栈节点

Nodecurrent=stack.pop();

process(current);//处理当前节点

//(2b)获取并处理邻接节点（按特定顺序，如逆序以优先访问未访问的）

Listneighbors=getNeighbors(current);

//例如，按列表原始顺序的反序处理邻接节点：

for(inti=neighbors.size()-1;i>=0;i--):

Nodeneighbor=neighbors[i];

if(!visited.contains(neighbor)):

stack.push(neighbor);

visited.add(neighbor);

//(3)结束条件（自然在循环结束时达成）

```

（三）邻接表迭代实现

结合邻接表（一种高效的图表示方法）和栈的迭代实现，可以清晰地管理节点的访问状态和遍历顺序，特别适用于需要显式控制或处理特定邻接节点顺序的场景。

1.算法步骤详解：

(1)初始化：创建一个空栈用于模拟递归调用栈，创建一个空集合用于记录已访问节点。将起始节点入栈并标记为已访问。

(2)循环处理栈非空：当栈不为空时，执行以下操作：

a.出栈节点：从栈顶弹出一个节点，记为`current`。

b.处理节点：对`current`节点进行处理。

c.准备访问邻接节点：获取`current`节点的所有邻接节点列表。

d.反向遍历邻接节点：为了确保在将邻接节点入栈时，它们是按照期望的顺序（例如，先访问编号较小的邻接节点，或者与邻接表存储顺序一致）被处理的，通常需要将邻接节点列表进行反转。然后，遍历反转后的邻接节点列表：

i.对于每一个邻接节点`neighbor`：

-检查`neighbor`是否已被访问。如果未访问：

-将`neighbor`节点入栈。

-将`neighbor`标记为已访问。

-如果`neighbor`已访问，则忽略。

(3)结束条件：当栈为空时，遍历结束。

2.示例代码（伪代码-邻接表迭代）：

```

voidadjacencyListDFS(Nodestart):

if(start==null):

return;

Stackstack=newStack();

Setvisited=newHashSet();

//(1)初始化：起始节点入栈并标记

stack.push(start);

visited.add(start);

//(2)循环处理栈非空

while(!stack.isEmpty()):

//(2a)出栈节点

Nodecurrent=stack.pop();

process(current);//处理当前节点

//(2b)获取当前节点的邻接节点列表

Listneighbors=getNeighbors(current);

//(2c)反向遍历邻接节点列表

for(inti=neighbors.size()-1;i>=0;i--):

Nodeneighbor=neighbors[i];

if(!visited.contains(neighbor)):

stack.push(neighbor);

visited.add(neighbor);

//(3)结束条件（自然在循环结束时达成）

```

三、深度优先遍历的应用场景

深度优先遍历因其探索路径的特性，在多种场景下非常有用。以下是一些典型的应用：

1.连通性判断：

(1)判断无向图是否连通：从任意一个节点开始进行深度优先遍历。遍历结束后，如果所有节点都被访问过，则图是连通的；否则，图是不连通的（至少存在两个不连通的分量）。

(2)查找无向图的连通分量：从未访问的节点开始进行深度优先遍历，遍历过程中访问到的所有节点属于同一个连通分量。对每个未访问的节点重复此过程，即可找到所有连通分量。

2.路径寻找：

(1)查找简单路径：虽然广度优先搜索（BFS）通常能找到最短路径，但DFS可以用来查找是否存在一条从起点到终点的路径，尤其是在不关心路径长度的情况下。

(2)检测环：在遍历过程中，如果遇到一个节点，其某个邻接节点已经被访问过（且不是直接父节点），则图中存在环。

3.拓扑排序：

(1)在有向无环图（DAG）中：拓扑排序是一种将图中所有节点排成一个线性序列，使得对于每一条有向边(u,v)，节点u在序列