IT评测·应用市场-qidao123.com技术社区

标题: 深入明白全排列算法：DFS与回溯的完美结合 [打印本页]

---

作者: 种地    时间: 2025-4-11 10:50
标题: 深入明白全排列算法：DFS与回溯的完美结合
全排列问题是算法中的经典问题，其目的是将一组数字的全部大概排列组合列举出来。本文将详细解析怎样通过深度优先搜索（DFS）和回溯法高效生成全排列，并通过模拟递归过程资助读者彻底掌握其核心思想。

---

问题形貌

给定一个正整数 n，生成数字 1 到 n 的全部排列。例如，当 n = 3 时，输出应为：
  

1. 1 2 3
2. 1 3 2
3. 2 1 3
4. 2 3 1
5. 3 1 2
6. 3 2 1

复制代码

算法思路

1. 核心变量

• path[N]：存储当前生成的排列。
  
• dt[N]（bool 数组）：标记数字是否已被使用（避免重复）。
  
• n：排列的长度（如 n=3 表示生成 1,2,3 的全排列）。
  

2. DFS递归函数

  

1. void dfs(int u) {
2.     if (u == n) {  // 终止条件：排列已填满
3.         print_permutation();  // 输出当前排列
4.         return;
5.     }
6.     for (int i = 0; i < n; i++) {
7.         if (!dt[i]) {  // 如果数字i未被使用
8.             path[u] = i;  // 选择i
9.             dt[i] = true;  // 标记为已使用
10.             dfs(u + 1);   // 递归填充下一位
11.             dt[i] = false; // 回溯：恢复状态
12.         }
13.     }
14. }

复制代码

3. 主函数

  

1. int main() {
2.     scanf("%d", &n);
3.     dfs(0);  // 从第0位开始生成排列
4.     return 0;
5. }

复制代码

递归过程模拟（以n=2为例）

初始状态

• n = 2（排列长度为 2，数字为 1, 2，对应内部 0, 1）。
  
• path = [?, ?]（未初始化）。
  
• dt = [false, false]（初始均未使用）。
  

---

递归调用树

第一层调用：dfs(0)

• 当前位 u = 0（正在添补 path[0]）。
  
• 循环 i = 0：
  
  
  
  • dt[0] 为 false，选择数字 0（实际输出为 1）。
    
  • 更新状态：
    
    
    
    • path = [0, ?]。
      
    • dt = [true, false]。
      
    
    
  • 递归进入 dfs(1)。
    
  
  

第二层调用：dfs(1)

• 当前位 u = 1（正在添补 path[1]）。
  
• 循环 i = 0：
  
  
  
  • dt[0] 为 true，跳过。
    
  
  
• 循环 i = 1：
  
  
  
  • dt[1] 为 false，选择数字 1（实际输出为 2）。
    
  • 更新状态：
    
    
    
    • path = [0, 1]。
      
    • dt = [true, true]。
      
    
    
  • 递归进入 dfs(2)。
    
  
  

第三层调用：dfs(2)

• 终止条件：u == n（2 == 2），打印当前排列：
  
  
  
  • 输出 path[0]+1, path[1]+1 → 1 2。
    
  
  
• 返回上一级（回溯到 dfs(1)）。
  

回溯到 dfs(1)

• 恢复状态：
  
  
  
  • dt[1] = false（dt = [true, false]）。
    
  
  
• 循环结束，返回上一级 dfs(0)。
  

回溯到 dfs(0)

• 恢复状态：
  
  
  
  • dt[0] = false（dt = [false, false]）。
    
  
  
• 继续循环 i = 1：
  
  
  
  • dt[1] 为 false，选择数字 1（实际输出为 2）。
    
  • 更新状态：
    
    
    
    • path = [1, ?]。
      
    • dt = [false, true]。
      
    
    
  • 递归进入 dfs(1)。
    
  
  

第二层调用：dfs(1)

• 当前位 u = 1。
  
• 循环 i = 0：
  
  
  
  • dt[0] 为 false，选择数字 0（实际输出为 1）。
    
  • 更新状态：
    
    
    
    • path = [1, 0]。
      
    • dt = [true, true]。
      
    
    
  • 递归进入 dfs(2)。
    
  
  

第三层调用：dfs(2)

• 打印排列：path[0]+1, path[1]+1 → 2 1。
  
• 返回上一级（回溯到 dfs(1)）。
  

回溯到 dfs(1)

• 恢复 dt[0] = false（dt = [false, true]）。
  
• 循环结束，返回 dfs(0)。
  

回溯到 dfs(0)

• 恢复 dt[1] = false（dt = [false, false]）。
  
• 循环结束，程序终止。
  

最终输出

  

1. 1 2
2. 2 1

复制代码

关键步调总结

• 递归向下：逐层选择未被使用的数字，更新 path 和 dt。
  
• 回溯向上：在每一层递归返回时恢复 dt 的状态，确保其他分支能精确使用数字。
  
• 终止条件：当 path 填满时立刻输出结果。
  

---

递归树图示

  

1. dfs(0)
2. │
3. ├─ i=0 (选1)
4. │  ├─ dfs(1)
5. │  │  ├─ i=1 (选2) → dfs(2) → 输出 [1, 2]
6. │  │  └─ 回溯：释放2
7. │  └─ 回溯：释放1
8. │
9. └─ i=1 (选2)
10.    ├─ dfs(1)
11.    │  ├─ i=0 (选1) → dfs(2) → 输出 [2, 1]
12.    │  └─ 回溯：释放1
13.    └─ 回溯：释放2

复制代码

关键点总结

• DFS的作用：递归地尝试全部大概的数字选择，直到填满整个排列。
  
• 回溯的必要性：在递归返回时恢复 dt 数组的状态，确保后续分支能精确选择数字。
  
• 时间复杂度：O(N×N!)，因为共有 N! 种排列，每种排列需要 O(N) 时间生成。
  

---

优化与扩展

• 非递归实现：可以用栈模拟递归，避免递归深度过大（但对小规模 n 影响不大）。
  
• 字典序排列：调整循环顺序，使输出按字典序排列。
  
• 去重排列：假如输入包含重复数字，需额外判断避免重复排列。
  

---

完备代码（C语言）

[code][/code]         通过DFS和回溯的结合，我们可以高效地生成全排列。明白递归的睁开与回溯是掌握该算法的关键。盼望本文的逐步解析能资助你彻底掌握这一经典问题！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4