DFS（深度优先搜索，Depth-First Search）算法是一种用于遍历或搜索树或图的算法。在执行搜索时，DFS会尽可能深地沿着树的分支进行，当节点v的所有出边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。如果还有其他的节点未被发现，则选择其中一个作为源节点并重复上述过程，整个过程重复进行，直到所有节点都被访问为止。

### DFS的基本步骤

1. **初始化**：将起始节点标记为已访问，并将其放入当前路径中。
2. **探索**：从当前节点出发，访问一个未访问过的邻接点，将其标记为已访问，并将其加入当前路径。
3. **回溯**：如果当前节点没有未访问的邻接点，则将其从当前路径中移除，并返回到上一个节点继续搜索。
4. **结束条件**：当所有可能的路径都被探索完毕，算法结束。

### DFS的伪代码

```
DFS(G, start vertex):
    let S be a stack
    S.push(start vertex)
    mark start vertex as visited

    while S is not empty:
        node = S.pop()
        for each neighbor of node:
            if neighbor is not visited:
                mark neighbor as visited
                S.push(neighbor)
```

### DFS的Python实现

```python
# 使用递归实现DFS
def dfs(graph, vertex, visited):
    if vertex in visited:
        return
    print(vertex)  # 访问节点
    visited.add(vertex)
    for neighbor in graph[vertex]:
        dfs(graph, neighbor, visited)

# 使用栈实现DFS
def dfs_iterative(graph, start_vertex):
    visited = set()
    stack = [start_vertex]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            print(vertex)  # 访问节点
            visited.add(vertex)
            for neighbor in reversed(graph[vertex]):  # 逆序遍历邻接列表，保证先进后出
                if neighbor not in visited:
                    stack.append(neighbor)

# 示例图的邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 调用DFS函数
dfs(graph, 'A', set())
dfs_iterative(graph, 'A')
```

在这个例子中，我们展示了两种实现DFS的方法：递归和迭代。递归方法更简洁直观，而迭代方法使用栈来模拟递归过程，避免了递归可能导致的栈溢出问题。

### DFS的应用

- **路径寻找**：在图中寻找从一个顶点到另一个顶点的路径。
- **拓扑排序**：在有向无环图（DAG）中进行拓扑排序。
- **连通性问题**：判断图的连通分量。
- **解决迷宫问题**：在迷宫中寻找从起点到终点的路径。

DFS是一种基础且强大的图遍历算法，广泛应用于计算机科学的多个领域。掌握DFS对于理解和解决复杂的图相关问题至关重要。