一，知识点总结
1.深搜（dfs）
①迷宫类深搜是在不撞墙，不越界的情况下，不断搜索回溯再搜索， 直到找到新的出路或从原路返回入囗无解为止。
核心代码：
for(int i=0;i<=3;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&vis[nx][ny]==0){
vis[nx][ny]=1;
dfs(nx,ny);
vis[nx][ny]=0;
}
}
②洪水填充指从一个起始节点开始把附近与其连通的节点提取出或填充成不同颜色， 直到封闭区域内的所有节点都被处理过为止， 是从一个区域中提取若干个连通的点与其他相邻区域区分开的算法。
核心代码：
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#' && !vis[nx][ny]) {
vis[nx][ny] = 1;
dfs(nx, ny);
}
}
③枚举类搜索是用不断递归来实现暴力枚举问题的。
核心代码：
void f(int x){
if(x==n+1){
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
a[x]=i;
f(x+1);
}
cout<<endl;
}
2.广搜（bfs）
①迷宫类广搜是用队列实现从起始点开始不段便利该点四周非越界，非撞墙的点，直到到终点的搜索方式，适合求迷宫最小步数。
核心代码：
s.push(node{x,y,0});
while(!s.empty()){
node now=s.front();
s.pop();
for(int i=0;i<8;i++){
int dx=now.x+nx[i];
int dy=now.y+ny[i];
if(dx==c&&dy==d){
cout<<now.cnt+1;
return;
}
if(dx<n&&dx>=0&&dy>=0&&dy<n&&vis[dx][dy]==0){
vis[dx][dy]=1;
s.push(node{dx,dy,now.cnt+1});
}
}
}
②洪水填充指从一个起始节点开始把附近与其连通的节点提取出或填充成不同颜色， 直到封闭区域内的所有节点都被处理过为止， 是从一个区域中提取若干个连通的点与其他相邻区域区分开的算法。
核心代码：
queue<node>q;
vis[a][b]=0;
q.push({a,b});
while(q.size()){
node now=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=now.x+dx[i];
int ny=now.y+dy[i];
if(nx<1 || ny<1 || nx>n || ny>m || vis[nx][ny]==1 || mp[nx][ny]=='.'){
continue;
}
if(mp[nx][ny]=='.'){
vis[nx][ny]=0;
}
q.push({nx,ny});
vis[nx][ny]=1;
}
}
3.树（T）
①树是一种非线性的数据结构， 它由若干个节点和它们之间的连接边组成， 通常用来表示具有层级关系的数据结构。树的定义是递归的， 每个节点可以看作一棵子树的根节点。一个树包含一个根节点和若干棵子树。
②树的知识点：
㈠节点的度：节点拥有的孩子（子树，分支）个数。
㈡树的度：所有节点中度数最大的节点度数
㈢树的的深度（高度）：树中节点的最大层数。
㈣树的宽度：树中最多节点那一层的节点数。
㈤根节点，起始节点，最上方的节点。一棵树至少有一个结点，这个结点就是根结点。
㈥叶子结点（终端结点）：度为0的结点。（ 没有再往下分支的节点）
㈦父结点（双亲结点）：下方节点的上结点。
㈧孩子结点：上方节点的下结点。
㈨兄弟结点：同一个父结点的多个子结点互为兄弟结点。
㈩祖先结点：从根结点到某个子结点所经过的所有结点， 为这个结点的祖先
（十一）子孙结点：以某个结点为根的子树中的任一结点， 该结点的子孙
③二叉树（BT）的每个节点最多有两个子节点。每个节点的子节点分别称为左孩子、右孩子， 它的两棵子树分别称为左子树、右子树。
㈠满二叉树：指一棵深度为k 且具有2k 一1 个节点的二叉树成为满二叉树。（ 每层都是满的）
㈡完全二叉树： 树中所含的结点和满二叉树中结点编号一一对应。叶节点只能出现在最下层和次下层。最后一层的结点都集中在该层最左边的若干位置。
㈢二叉树的性质：
⑴第k层最多2^（k-1）个节点
⑵深度为h的二叉树最多有2^h-1个节点（k>=1）
⑶n个节点的完全二叉树深度log2（n)+1
⑷度为0节点=度为2节点+1
⑸若设二叉树的深度为h，除第h层外，其他各层（1~h-1）的节点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树
④树的存储
㈠邻接矩阵
使用n * n 的二维数组来存储n 个点的树， 每一个元素表示其两下标对应的点之间边的有无构建代码模板：
核心代码：
memset(a,0,sizeof(a));
for(int i=0;i<n-1;i++){
cin>>x>>y;
a[x][y]=1;
}
㈡邻接表
使用n 个向量(vector[ ]) 实现， 每一个向量存对应节点的所有相连的点（ 视情况可不存父节点） 构建代码模板
核心代码：
vector<int>a[100005];
for(int i=2;i<=n;i++){
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
⑤树的遍历：
㈠先序遍历： 根左右。若为空树， 什么都不做，否则：访问根结点；先序遍历左子树；先序遍历右子树。
㈡中序遍历： 左根右。 若为空树， 什么都不做，否则：中序遍历左子树；访问根结点；中序遍历右子树。
㈢后序遍历： 左右根。 若为空树， 什么都不做，否则：后序遍历左子树；后序遍历右子树；访问根结点。
㈣树的dfs便利：
核心代码：
void dfs(int x){
for(int i=1;i<=n;i++){
if(a[i][x]=='1'&&vis[i]==0){
vis[x]=1;
cout<<i<<" ";
dfs(i);
}
}
return;
}
4.图
①图的简介
㈠有向图： 图的边为有向边（ 弧） 时， 为有向图。有向图的弧记为< v ， w > ， 其中v ， w 是顶点， v 是弧尾， w 是弧头。称为从顶点v 到顶点w 的弧。
㈡无向图： 图的所有边都没有方向性时， 为无向图。无向图的弧记为(v,w), 其中v ， w 是弧所连接的顶点， 两个顶点的顺序没有要求。
㈢顶点的度： 顶点的度为连接该顶点的边的数目； ^ 对于有向图， 度可以分为出度和入度， 出度+入度= 度。入度以该顶点为终点。出度以该顶点为起点。*无向图中， 度数之和为边数的2 倍；有向图中， 全部顶点入度之和= 全部顶点出度之和= = 边数；
㈣子图： 若图a 的所有顶点、边都能在图b 中找到， 则a 为b 的子图
㈤完全图： 图的任意两个顶点都可以直接到达时， 为完全图； ^ 有向完全图中， 任意两个顶点间都有方向相反的边； 含有n 个顶点的有向完全图中， 边有n （ n 一1 ） 条； * 含有n 个顶点的无向完全图中， 边有n 〔n 一1 ） / 2 条；
㈥路径： 从一个顶点到另一个顶点的顶点序列为路径。* 顶点不重复出现， 为筒单路径。路径的长度是路径上的边的数目。
㈦回路（ 环） ： 第一个顶点（ 起点） 和最后一个顶点（ 终点） 相同的路径为回路或环。自己出发， 终回到自简单回路或简单环： 除了起点和终点之外， 其余顶点不重复出现；
㈧连通： 一个顶点到另一个顶点有路径， 则这两个顶点是连通的（ a 出发， 能到b ， 则a ， b 连通） * 图中任意两个
②图的存储
㈠邻接矩阵
使用n * n 的二维数组来存储n 个点的树， 每一个元素表示其两下标对应的点之间边的有无构建代码模板：
核心代码：
memset(a,0,sizeof(a));
for(int i=0;i<n-1;i++){
cin>>x>>y;
a[x][y]=1;
}
㈡邻接表
使用n 个向量(vector[ ]) 实现， 每一个向量存对应节点的所有相连的点（ 视情况可不存父节点） 构建代码模板
核心代码：
vector<int>a[100005];
for(int i=2;i<=n;i++){
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
③图的类型
零图： 边集为空集的图树： 边数比节点数少1 的连通图森林： m (m>=0) 棵互不相交的树菊花图： 所有点都和同一个点相连链图： 一个点连接一前一后两个点， 所有点形成了一条链仙人掌： 不含自环的， 一条边最多属于一个简单环的无向连通图* 完全图． N 个顶点的图， 有№ 〔N 一1 ） / 2 条边。也是原图（ 原本的图） 十补图* 补图： 若邻接则改为非邻接， 若非邻接则改为邻接， 得到的图为原图的补图* 简单图． 不含重边和自环的图。零图： 边集为空集的图。树： 边数比节点数少1 的连通图。森林： m (m>-=o) 棵互不相交的树。菊花图： 所有点都和同一个点相连。链图： 一个点连接一前一后两个点， 所有点形成了一条链。仙人掌： 不含自环的， 一条边最多属于一个简单环的无向连通图。* 完全图： N 个顶点的图， 有№ 〔N 一1y2 条边。* 补图： 若邻接则改为非邻接， 若非邻接则改为邻接， 得到的图为原图的补图。* 完全图： 原图十补图。* 简单图： 不含重边和自环的图。
④图的便利
㈠图的dfs便利
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,s,vis[N];
vector<int>a[N];
void dfs(int k){
cout<<k<<" ";
for(int i=0;i<a[k].size();i++){
if(vis[a[k][i]]==0){
vis[a[k][i]]=1;
dfs(a[k][i]);
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
vis[s]=1;
dfs(s);
return 0;
}
㈡图的bfs便利
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,s,vis[N];
vector<int>a[N];
queue<int>q;
void bfs(int k){
q.push(k);
vis[k]=1;
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;i<a[now].size();i++){
if(!vis[a[now][i]]){
vis[a[now][i]]=1;
q.push(a[now][i]);
cout<<a[now][i]<<" ";
}
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
cout<<s<<" ";
bfs(s);
return 0;
}
5.动态规划：
①动态规划是一种将复杂问题分解为一系列相互关联的子问题，并通过求解子问题的最优解来构建原问题最优解的算法思想。它通常用于解决具有最优子结构性质和重叠子问题的问题，通过避免重复计算子问题，大大提高了计算效率。
②最优子结构：
问题的最优解可以由子问题的最优解组合而成。例如，在背包问题中，背包容量为 5 时的最优装法， 可以由背包容量为 4 等更小容量的最优装法加上放入或不放入某个物品来确定。
③重叠子问题：
在求解问题的过程中，会反复出现相同的子问题。如在计算斐波那契数列时，计算 F (n) 需要多次计算 F (n-1)、F (n-2) 等子问题。
6.背包
㈠背包问题一般可以描述为：给定一组物品，每个物品都有自己的重量和价值，在限定的背包容量下，选择哪些物品放入背包中，使得背包中物品的总价值最大。
㈡0-1 背包问题：
每个物品只有两种选择，要么放入背包，要么不放入背包，不能将物品进行拆分。例如，背包容量为 5 千克，有 3 个物品，分别是重量 2 千克、价值 3 元的物品 A，重量 3 千克、价值 4 元的物品 B，重量 1 千克、价值 2 元的物品 C，需要在有限容量下选择物品组合以达到最大价值。
㈢完全背包问题：每种物品可以无限次地放入背包中。比如，有无限个重量为 2 千克、价值 3 元的物品 A，无限个重量为 3 千克、价值 4 元的物品 B 等，在给定背包容量下求最大价值。
㈣多重背包问题：
每种物品有一定的数量限制。例如，物品 A 有 2 个，物品 B 有 3 个等，然后在背包容量限制下计算能获得的最大价值。
㈤分组背包：
有N组物品，每组包含若干个物品，一个容量为 V的背包。每组物品中的物品相互冲突，即每组最多只能选一个物品放入背包。每个物品有各自的重量 w 和价值 v，目标是在不超过背包容量的前提下，选择物品使得背包内物品的总价值最大。
可参考