DFS 算法如何应用于拓扑排序问题

# 1. 初识深度优先搜索（DFS）

#### 1.1 什么是图算法？
图算法是解决图结构相关问题的一类算法。图是由节点（顶点）和边组成的一种数据结构，常见的应用领域包括社交网络分析、路线规划等。图的基本概念包括顶点、边、度等。图可以通过邻接矩阵或邻接表表示。

#### 1.2 深度优先搜索简介
深度优先搜索（DFS）是一种常见的图遍历算法，其特点是尽可能深地搜索图的分支。DFS的基本思想是递归或借助栈，沿着图的某一条路径尽可能深地搜索，直到无法继续为止。DFS的算法流程包括访问当前节点、递归访问相邻节点等步骤。

# 2. 深度优先搜索在遍历问题中的应用

#### 2.1 二叉树中的深度优先搜索

深度优先搜索（Depth First Search，DFS）是一种常用的图搜索算法。在二叉树中，DFS常被应用于遍历树的所有节点。通过深度优先搜索，可以按照树的深度优先顺序逐个访问节点，包括先序遍历、中序遍历和后序遍历三种方式。

##### 2.1.1 二叉树遍历方式

在二叉树遍历中，包括先序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）三种方式。这些遍历方式均可以利用深度优先搜索实现。

##### 2.1.2 递归实现深度优先搜索

递归是实现深度优先搜索的一种常用方法。通过递归地访问左子树和右子树，可以实现二叉树的深度优先搜索遍历。

以下是使用递归实现先序遍历的示例代码（Python）：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def dfs_preorder(root):
    if root is None:
        return
    print(root.val)  # 先访问根节点
    dfs_preorder(root.left)  # 递归访问左子树
    dfs_preorder(root.right)  # 递归访问右子树

# 示例二叉树
#        1
#       / \
#      2   3
#     / \
#    4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

dfs_preorder(root)

##### 2.1.3 非递归实现深度优先搜索

除了递归实现外，还可以使用栈（Stack）来实现非递归的深度优先搜索。通过维护一个栈，可以模拟递归的过程，按照深度优先的顺序访问节点。

下面是使用栈实现先序遍历的示例代码（Python）：

def dfs_preorder_iterative(root):
    if root is None:
        return
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.val)  # 访问当前节点
        if node.right:  # 先压入右子节点，再压入左子节点
            stack.append(node.right)
        if node.left: