完全图：每两个点都有边相连
邻接顶点，有两条边连接
子图：边和点都是子集
顶点的度：与之相关联的边的条数，有向图种是出度和入度的和
简单路径：顶点不重复
回路：起点和终点是重复的
连通图：每两个顶点都是联通的，就是有路径能到就行，不一定是直达，如果不是连通图，那么极大连通子图就是连通分量
强连通图：针对有向图而言，如果对于每两个点都有双向的路径，那么就是强连通图，分量的定义和上面是类似的
生成树，连通图的生成树是极小连通子图，n个顶点n-1条边，一条都不会多
表示方法：邻接矩阵和邻接表，邻接表就是表示这个链的节点和头节点都是有边的，对于有向图就会有出边表和入边表（也叫逆邻接表）
图的遍历方法
深度优先搜索和广度优先搜索
连通分量，对于一个不连通的图，只有一次出发的时候是不可能全到达的。从每一个点判断，如果走过就一定是在某个连通分量里了，反之就遍历生成了一个连通分量，所有连通分量的生成树形成了生成森林
kruskal算法和prim算法
krskal算法：排序边，并查集取舍，就是说所有的点都先是断开的，然后开始找最小的边接起来，其中不可以出现环，也就是属于同一个联通分支的，也就是这个时候并查集发挥了作用
prim算法就是选一个初始的顶点，然后对这个所有点的边进行选择最小的，然后顶点集就加了一个，然后对这个顶点集里的所有点对那些不在顶点集的点的边里找一个最小的出来，这个时候的处理办法一种就是把顶点集可能会引申增加的边都放在一个堆里，然后进行选择，或者就是使用一个辅助的数组，数组里面保存的是当前的顶点集里面到各个点的距离，然后每一次加入一个点的时候尽心一次遍历更新
Dijkstra算法就是松弛路径，一开始的初始化，然后找到从出发点到所有还没有被加入到路径里的点里的最短的路径的点，加入到可到达集合里，然后在看看由于这个新的节点的加入，能不能使得出发点到其他点的距离减小，这样子反复的进行
这个算法只能够处理没有负数的路径，对于有负数的路径可以考虑一下floyd算法，似乎是求传递闭包的那个。这个算法就是对角线移动
有向无环图表示一个工程里面每一个项目的先后工作关系，一定是需要满足一个基本的条件就是没有环！
所以可以考虑一下使用拓扑排序进行一系列的处理
拓扑排序的思路就是先从入度为0的开始顶点开始删除，删除点又删除边的，一直重复，最后若有人始终不输出就是存在有向环。实现的方法就是设置一个存放入度为0的顶点栈
认为总的花费时间复杂度O（n+e）
时至今日我才发现AOV是用顶点构造出来的活动网络，边上是没有权值的，只是依靠拓扑进行排序链接，有权值的活动网络叫做AOE，是需要求解出关键路径的，有顶点的最早最晚，还有边的最早最晚四个参数。
对于排序算法分析往往是围绕着比较次数和交换次数进行的
直接插入排序 n^2 稳定
折半插入排序的比较次数的性能有所上升是nlogn的，但是交换次数依旧是取决于初始的序列的
对于快速排序的优化，1.小规模使用直接插入排序 2.小规模直接终止排序，然后直接插入排序 3.使用三个值选择作为中间值
竞标赛排序是使用数组排序的，里面的操作也几乎都是使用二分的规模
简单的记录一下这几个复杂度的来源
直接插入：最好的比较就是对当前数向之前比是大于，没必要再比较，每次都这样，那就比较了n次没有交换
最差的时候就是逆序，每一个都要一直比较到最前面，而且对于插入排序是往前比就会交换所以就是n个数每次都是n
折半插入使得每次查找就是折半就是nlogn，然后交换和直接插入一样
起泡排序，最好的时候就是两两比较啥都不交换，标志位标记不发生交换结束遍历，也就是n的比较和0的交换
最坏的就是逆序，每次都交换，每次都比较
快速排序，快排的核心就是以第一个作为分界线，对当前的序列进行分界，或者是说把当前的分界线进行定位，最好的就是每一次都选的好的分界线，都是一分为二的，然后就是分了logn次，每一次都在内部比较，合起来就是n的，一共就是nlogn，移动就是每一次都只需要把分界线的值移动就可以了
最坏的时候就是每一次选择的分界线都分的一边倒，使得分了n次，然后同理比较就是n^2的了，最坏的就是要每一次都交换，比如说选最左边的，但是右边的值都比较小，就都要换到左边去
监视哨
举个例子就是在搜索一个序列里是否有等于k的元素的时候，把数组的结尾的结尾的位置赋值为k，然后进行循环，循环的条件只要是设置为等于的时候跳出就可以了，同时找到了就会正常的结束循环，就算是没有找到，也会触发末尾的条件而结束。就不用考虑越界的问题了，同时对于没有找到的条件判断也很简单，就是是否到达了末尾
失败节点
没有找到的时候才会遇到的节点，也就是叶子节点
事实上m路搜索树就是：每一个节点含有一些数，这个数是分解点，一个数把子区间一分为二，比如说现在有 1 2 3 4 5 6这几个数，那么取2和4留在这个父节点了，其余的节点被区分为1 || 3 || 5 6，这样子就形成了三个分支。m=3
B+树删除的总结就是
1：直接是根和叶，自己的节点数量还多，直接删除就行
2：是叶不是根，自己的节点还是很多，直接删除就可以了
3：自己的节点不太够，但是兄弟的够，所以就找兄弟借，父节点下来一个，兄弟的上去
4：兄弟的也不够了，只能是找父节点去借了
问题
为什么在B树的删除里不是选取的是被删除的节点所指向的子树的叶节点吗，为什么一定是右子树的
答：似乎都是按照的是当前数字的右边的那个子树作为目标子树