下面是笔记：
1.广度优先搜索是什么
将起始节点标记为已访问，并将其加入到队列中。
当队列不为空时，从队列的头部取出一个节点，依次访问它的相邻节点。
如果相邻节点未被访问，则将其标记为已访问，并将其加入到队列的尾部。
重复步骤2和步骤3，直到队列为空或者找到目标节点。
2、遇到一个新的岔路，两个岔路同时搜索
3、一条路到了死路，其他路继续
4、找到终点，此时可以结束，终点的步数必为最短步数
5、或是不结束（依据题意），直到将图全部搜索完
广度优先搜索（模板）
void bfs(起点)
{
初始化队列;
起点入队，标记走过;
while(队列不为空)
{
if(到达终点)
{
打印结果;
return;
}
for(枚举队首能通达的所有节点)
{
if(条件成立)
{
节点入队;
标记;
}
}
}
}
深搜优先往深处找，不撞南墙终不悔。像是一个人走迷宫，遇见岔路不知道怎么走，就瞎选一个（程序中一搬从头遍历），走到底，不对，回到岔路口，选另一条路，接着走。
树是一种非线性的数据结构，它由若干个节点和它们之间的连接边组成，通常用来表示具有层级关系的数据结构。
树的定义是递归的，每个节点可以看作一棵子树的根节点。一个树包含一个根节点和若干棵子树，而每棵子树也可以看作是一棵树。
1、节点的度：
节点拥有的孩子（子树、分支）个数。
2、树的度：
所有节点中度数最大的节点度数。
3、树的深度（高度）：
数中节点的最大层次。
4.树的宽度：
数中最多节点那一层的节点数。
5、根节点：
起始节点、最上方的节点。
*一棵树至少有一个结点，这个结点就是根结点。
6、叶子结点（终端结点）：
度为0的结点。
（没有再往下分支的节点）
7、父结点 （双亲结点）：
下方节点的上端结点。
8、孩子结点：
上方节点的下端结点。
9、兄弟结点：
同一个父结点的多个子结点互为兄弟结点。
10、祖先结点：
从根结点到某个子结点所经过的所有结点，为这个结点的祖先
11、子孙结点：
以某个结点为根的子树中的任一结点，该结点的子孙
树的存储和遍历（模板）
1、邻接矩阵
使用n * n的二维数组来存储n个点的树，每一个元素表示其两下标对应的点之间边的有无 构建代码模板：
int n,tre[1001][1001];
int main(){
cin>>n;
//存储
for(int i=1;i<=n-1;i++){ //n-1条边
int x,y;
cin>>x>>y; //读入两个顶点序号
tre[x][y]=1;
tre[y][x]=1; //对称性
}
//遍历
for(int i=1;i<=n;i++){
cout<<i<<" "; //输出当前遍历到的点
for(int j=1;j<=n;j++) //遍历邻居
if(tre[i][j]==1)
cout<<j<<" ";
cout<<endl;
}
}
2、邻接表
使用n个向量（vector
vector<int> tre[100001];
int n;
int main(){
cin>>n;
//存储
for(int i=1;i<=n-1;i++){ //n-1条边
int x,y;
cin>>x>>y; //读入两个顶点序号
tre[x].push_back(y);
tre[y].push_back(x); //对称性
}
//遍历
for(int i=1;i<=n;i++){
cout<<i<<" "; //输出当前遍历到的点
for(int j=0;j<tre[i].size();j++)//遍历邻居
cout<<tre[i][j]<<" ";
cout<<endl;
}
}
先序遍历：根左右
若为空树，什么都不做，
若为空树，什么都不做，
若为空树，什么都不做，
1、找到该树的先(后)序遍历的起始(最后)一个元素（必为根结点）
图是一种非常重要的数据结构，它是由一组顶点和一组边组成的。节点通常表示对象，边表示它们之间的关系。可以用来描述各种实际问题，比如网络、社交关系、路径规划等等。
有向图： 图的边为有向边（弧）时，为有向图。 有向图的弧记为<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连通） *图中任意两个顶点都是连通的，为连通图。
图的存储
1、邻接矩阵
使用n * n的二维数组来存储n个点的图，每一个元素表示其两下标对应的点之间边的有无及其边权 构建代码模板：
for (i = 1; i <= m; i++) { //m条边
cin >> u >> v >> w; //读入两个顶点序号及权值（无权图则无w）
g[u][v] = w; //对于无权的图g[u][v]=1
g[v][u] = w; //无向图的对称性,如果是有向图则不要有这句！
}
2、邻接表
使用n个向量（vector
for (i = 1; i <= m; i++) //m条边(无权值)
{
cin >> u >> v; //读入两个顶点序号
g[u].push_back(v);
g[v].push_back(u); //无向图的对称性,如果是有向图则不要有这句！
}
struct node
{
int x, len;
};
for (i = 1; i <= m; i++) //m条边(有权值)
{
cin >> u >> v >> w; //读入两个顶点序号
g[u].push_back({v, w});
g[v].push_back({u, w}); //无向图的对称性,如果是有向图则不要有这句！
}
零图：边集为空集的图 树：边数比节点数少1的连通图 森林：m（m>=0）棵互不相交的树 菊花图：所有点都和同一个点相连 链图：一个点连接一前一后两个点，所有点形成了一条链 仙人掌：不含自环的，一条边最多属于一个简单环的无向连通图 完全图 ：N个顶点的图，有N补图 ：若邻接则改为非邻接，若非邻接则改为邻接，得到的图为原图的补图 *简单图 ：不含重边和自环的图
零图：边集为空集的图完全图：N个顶点的图，有N (N-1)/2条边
动态规划（Dynamic Programming，简称DP）是一种用来解决一类具有重叠子问题和最优子结构性质的问题的算法思想。
重叠子问题指的是在求解问题的过程中，会反复求解同一个子问题，导致算法效率低下。
最优子结构指的是问题的最优解可以通过子问题的最优解来构造。
定义状态：定义子问题的解以及问题的解。通常采用状态表示问题的某些属性或特征。
确定状态转移方程：确定从一个状态转移到另一个状态的具体方式。
初始状态：定义最小子问题的解或问题的初始解。
计算顺序：根据状态转移方程自底向上计算问题的解。
解释解：根据计算得到的解释解决方案。
最优化问题通常需要在所有可能的解中寻找最优解。这类问题通常可以使用动态规划来解决，它们具有最优子结构性质。在这种情况下，问题的最优解可以通过子问题的最优解得到。
1.广度优先搜索
