复习课——DFS

视频：

DFS复习视频

本期为复习课！！！

1、DFS总结

直接看思维导图即可。

2、DFS的思路。

一条路走到底。
无向图的DFS遍历：

有向图的DFS遍历：

3、如何完成一道DFS搜索问题。

1. 读题
2. 画出搜索树
3. 剪枝与优化
4. 敲出代码。

4、排列数字问题讲解+复习

以前在我的第一期分享里讲过。
现在复习一遍。
题目：
题目：
给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式

共一行，包含一个整数n。

输出格式
按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤7

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

这道题我们读完题后先画一下搜索树
比如我们用3的全排列举个例子。

这就是搜索树。
接下来我们分为两步讲解DFS的过程。

1、走到头就输出。

if(u == n)
{
    for(int i = 0; i < n; i ++) cout << path[i] << ' ';//输出
    cout << endl;
    return;
}

公式编辑器版：

2、没走到头就继续走，不撞南墙不回头，撞了南墙就回溯，走到头一起来输出（见上面）。（莫名押韵）

我们需要一个st数组来存每个点是否被遍历过。
然后循环一遍就行了。
最后一定要记得回溯！即还原现场。

for(int i = 1;i <= n; i ++)
{
    if(!st[i])
    {
        st[i] = true;
        path[u] = i;
        dfs(u + 1);//递归
        st[i] = false;//还原现场
        path[u] = 0;
    }
}

公式编辑器版：

你们要的完整代码：

#include<iostream>
#include<algorithm>

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])
        {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);//递归
            st[i] = false;//还原现场
            path[u] = 0;
        }
    }
}

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

稍微说一下剪枝，大家回去看看小猫爬山那道题，慢慢体会。

剪枝就是将一些部分减去。
比如小猫爬山那道题，如果当前值已经大于了最优解就不用继续搜了。
大家可以看一下那道题。

最后是一点小作业，大家做一下~

作业：
1. 写一遍n皇后问题，代码发到评论区，AC代码见后。
2. 复习小猫爬山，思考剪枝，代码不用发。（讲解在这里~，最大抑或对后面就是。）
3. 看看数独那道题，说出思路，写到评论区，有能力的发代码，下节课讲解~

n皇后代码，做完才能看哦

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int n;
char g[N][N];
bool c[N], d[N], dg[N];
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i ++) cout << g[i] << endl;
        cout << endl;
        return;
    }
    for(int i = 0; i < n; i ++)
    {
        if(!c[i] && !d[u + i] && !dg[n - u + i])
        {
            c[i] = d[u + i] = dg[n - u + i] = true;
            g[u][i] = 'Q';
            dfs(u + 1);
            c[i] = d[u + i] = dg[n - u + i] = false;
            g[u][i] = '.';
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            g[i][j] = '.';
    dfs(0);
    return 0;
}

好了本期分享就到这里了。

未经允许，请勿转载！

这是我的全部分享~

bye~