知识点总结
1.深度优先搜索（dfs）
深搜是指在搜索至不能继续搜索时退回上一步，继续往其他路径搜索的一种算法
深搜有许多类型，包括迷宫类、枚举类、洪水填充类
其中迷宫类包括：迷宫最短路径、迷宫路径数量、领地问题（也属于洪水填充）、八皇后
枚举类搜索包括：基本枚举、背包（另一种算法）
洪水填充类包括： 连通块问题
2.广度优先搜索 （bfs）
广搜是指从一个点一圈一圈搜索，像水波纹一样，也属于搜索
广搜和深搜一样有许多类型，包括迷宫类、枚举类、洪水填充类
其中迷宫类包括：迷宫最短路径、迷宫路径数量、领地问题（也属于洪水填充）、八皇后
枚举类搜索包括：基本枚举、背包（另一种算法）
洪水填充类包括： 连通块问题
插播：
深搜与广搜对比：
1.深搜的时间复杂度比广搜大的十分多
2.广搜的需要定义结构体与队列，占空间复杂度更大
3.深搜属于递归函数，但广搜只是单纯的循环
4. 在搜索中，深搜可以做所有，广搜有一些题目不可以做
3.树
树是指每一个父节点拥有多个子节点，而每个子节点只有一个父节点，形成了一对多的关系
关于树的题目需要存储两点之间（每条边），有两种：
邻接表、邻接矩阵
虽然都可以存储，但邻接表的空间比邻接矩阵小
树也可以通过深搜和广搜来写
节点的度：节点的子节点个数
树的度：树中最大节点的度
树的深度：树中节点的最大层次
树的宽度：树中最多节点的层次的节点数
根节点：最上方的节点，树开始的节点
叶子节点：度为0的节点
父亲节点：下方节点的上端节点
孩子节点：上方节点的下端节点
兄弟节点：拥有同一个父亲节点的多个节点
祖先节点：从根节点至某个子节点经过的所有点，成为这个节点的祖先节点
子孙节点：以某个节点为根的子树中的任意节点，成为其子孙节点
二叉树（BT）：
二叉树指每个父节点最多有2个子节点的树，所以拥有左子节点和右子节点
二叉树的遍历 ：
先序遍历：父节点->左子节点->右子节点
中序遍历：左子节点->父节点->右子节点
后序遍历：左子节点->右子节点->父节点
二叉树性质：
第k层最多有2^（k-1）个节点
深度为h的二叉树最多有2^h-1个节点
n个节点的完全二叉树深度为log2（n）+1
二叉树特殊类别：
满二叉树：一棵深度为k且具有2k-1个节点的二叉树
完全二叉树：一颗最下层少了任意个节点且剩余节点靠左的满二叉树
4.图
图是指每个节点可以到达多个节点，存在“多对多”的关系
有向图：
有向图：若 E 是有向边（也称弧）的有限集合，则图 G 为有向图。
弧是顶点的有序对，记为 <v,w>
其中 v 称为弧尾，w 称为弧头，<v,w > 称为从顶点 v 到顶点 w 的弧。
无向图：
若 E 是无向边（简称边）的有限集合，则图 G 为无向图。
边是顶点的无序对，记为 (v,w) 或 (w,v)
顶点 w 和顶点 v 互为邻接点。
连通：
在无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。在有向图中
若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径，则称这两个顶点是强连通的。
连通图与强连通图：
无向图中任意两个顶点都是连通的，则称图为连通图；
有向图中任何一对顶点都是强连通的，则称此图为强连通图。
顶点的度：
对于无向图，顶点 v 的度是指依附于该顶点的边的条数。
对于有向图，顶点 v 的度分为入度和出度，
入度是以顶点 v 为终点的弧的数目，出度是以顶点 v 为始点的弧的数目。
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，目标是在不超过背包容量的前提下，
选择物品使得背包内物品的总价值最大。
2 个赞
%%%orz
我感觉你们基础学的内容都快赶上我们普及了 
但是这些明明都是普及的啊
@huangfeidong ？这些都是基础的呀？（就比如他们没有学过：st表，倍增，树上 dp 数学 线段树 最小生成树 还有一些 STL 他们还没有学，不过他们也很厉害了，刚刚加入半年就把基础学完了
学完了？？？？？
半年？？、不是吧！！！！！！！
基础就这么点内容不用惊讶
哦。。。。。。。。。。。。。。
你说得对，但是 st 表，倍增，树上 dp，线段树，最小生成树是提高内容
你怎么知道我学状压DP学似了
我都觉得这些根本不是基础的
1 个赞
是基础的，我刚学完
4 个赞
今天最后一节课
3 个赞
只是没有学广搜
3 个赞
2 个赞