算法基础课

3.1 搜索与图论

1. 深度优先搜索(DFS)
2. 宽度优先搜索(BFS)
3. 树与图的存储
4. 树与图的深度优先遍历
5. 树与图的宽度优先遍历
6. 拓扑排序

1. 深度优先搜索(DFS)

搜索方式:一直向下搜,无路可走再返回上一层
人物品质:执着

例题1: 842.排列数字

链接
AC代码:

#include <iostream>
using namespace std;
const int N = 8;
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);
            st[i] = false;
            path[u] = 0;
        }
}
int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

2. 宽度优先搜索(BFS)

搜索方式:每次搜一层,一直向下搜所
人物品质:眼观六路,耳听八方,稳重

Tips 1.DFS VS BFS: