[编程笔记]-DFS深度优先搜索

简介

DFS(Deep First Search)，深度优先搜索，典中典，重中重。

作用

一般用来在图、树中进行搜索。

原理

过程可视作一棵树，每次向着子节点搜索，搜到叶节点就回溯，然后搜下一个子节点，直到把子节点搜完了就接着回溯。

实现

一般用栈来模拟，需要O(h)的空间

概念

回溯

就是从子节点回到父节点

剪枝

跳过已经遍历过的点减少时间复杂度。

代码

递归

这个太简单了，过(～￣▽￣)～

栈

这个嘛……说句实话不是很常用，而且和BFS的代码基本没有区别，所以就不写了。

挂个BFS，需要者自取：

[编程笔记]-BFS广度优先搜索

例题

这么典的算法，肯定要配一个超典的题型~

n皇后问题

AcWing843-n皇后问题

进阶版

为啥先讲进阶版？您是先学会用打火机还是先学会钻木取火？

由于每一行都只有一个皇后，所以遍历每一行就行了，整体思路根全排列一样。

给每个竖列、对角线都设立一个对应判断值，然后直接套板子。

#include<bits/stdc++.h>
using namespace std;

const int N=15;

int n;
int use[N];
bool vis[N]={false},deg[N*2]={false},fdg[N*2]={false};//deg->右倾对角线右侧顶点；fdg->左倾对角线右侧顶点

void dfs(int now){
    if(now==n+1){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(use[i]==j)cout<<'Q';
                else cout<<'.';
            }
            cout<<'\n';
        }
        cout<<'\n';
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]&&!deg[n-now+i]&&!fdg[now+i]){
            use[now]=i;
            vis[i]=deg[n-now+i]=fdg[now+i]=true;
            dfs(now+1);
            vis[i]=deg[n-now+i]=fdg[now+i]=false;
            
        }
    }
}

int main(){
    cin.tie(0);
    cin>>n;
    dfs(1);
    return 0;
}

原始版

暴力循环每一个格子——选or不选……选or不选……

然后每n²次对一下答案。

听起来就暴力极了。(^▽^)

//反正判断行列跟进阶版一样，然后思路又简单到爆炸，所以想必就不用我这个蒟蒻打了(^▽^)

例题2

毕竟是图论问题，还是来一道和图论关系大的吧。
AcWing846-树的重心

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int idk;
int ed[N*2],to[N*2],ne[N*2],hd[N];

int n;
int a,b;
int vis[N]={false};
int ans=0x3f3f3f3f;

void merge(int x,int y,int v=1){
    ed[++idk]=v;
    to[idk]=y;
    ne[idk]=hd[x];
    hd[x]=idk;
}

int dfsize(int now){
    vis[now]=true;
    int res=0,sum=1;
    for(int i=hd[now];i;i=ne[i]){
        if(!vis[to[i]]){
            int t=dfsize(to[i]);
            res=max(res,t);
            sum+=t;
        }
    }
    res=max(res,n-sum);
    ans=min(ans,res);
    return sum;
}

int main(){
    cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        merge(a,b);
        merge(b,a);
    }
    dfsize(n);
    cout<<ans;
    return 0;
}

完结撒花o(￣︶￣)o