第三講 搜索與圖論

DFS

• 首先考慮的就是順序

  • 全排列為例
  1. 3個(gè)空格
  2. 系統(tǒng)會(huì)有隱藏的棧幫忙做回溯
  3. 記錄的是當(dāng)前的路徑

• DFS搜索的順序可以看成一棵樹(shù)，其實(shí)就是遞歸

• 回溯一定要記住恢復(fù)現(xiàn)場(chǎng)

#include<iostream>
using namespace std;
const int N=10;
int n;
int path[N];//定義路徑
bool st[N];
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++)cout<<path[i]<<" "; 
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            path[u]=0;
            st[i]=false;
        }
    } 
}
int main()
{
    cin>>n;
    dfs(0);
    
    return 0;
}