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

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

1.1 什么是图算法？
1.2 深度优先搜索简介

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

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

2.1.1 二叉树遍历方式
2.1.2 递归实现深度优先搜索
2.1.3 非递归实现深度优先搜索

解锁专栏，查看完整目录
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 = rightdef dfs_preorder(root): if root is None: return print(root.val) # 先访问根节点 dfs_preorder(root.left) # 递归访问左子树 dfs_preorder(root.right) # 递归访问右子树# 示例二叉树# 1# / \# 2 3# / \# 4 5root = 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: