基本思想 数据结构 空间
DFS 一下子搜到底，然后再回溯 stack O(h) 与树高成正比 不具有最短性
BFS 每次搜一层 queue O(2h) 2h是节点的个数，最坏情况就是全存 如果权重是1，则可以搜出“最短路”

DFS

回溯和剪枝
空间复杂度是O(h)，因为每次都是只存一个分支，不是存一整棵数，回溯后就删除存的分支，重新存新的分支
模板题：全排列

  1. #include <iostream>
  2. using namespace std;
  3. const int N = 10;
  4. int n;
  5. int path[N];
  6. bool st[N];
  8. void dfs(int u)
  9. {
  10.     if(u==n)
  11.     {
  12.         for(int i = 0;i < n;i++) cout<<path[i]<<" ";
  13.         puts("");
  14.         return;
  15.     }
  16.     for(int i = 1;i<=n;i++) 
  17.     {
  18.         if(!st[i])
  19.         {
  20.             path[u] = i;
  21.             st[i] = true;
  22.             dfs(u+1);
  23.             st[i]=false;
  24.         }
  25.     }
  26. }
  28. int main()
  29. {
  30.     cin>>n;
  31.     dfs(0);
  32.     return 0;
  33. }

BFS

每次搜一层