常问面试算法
1.KMP算法
在主串中第i个字符与模式串中第j个字符“失配”时,仅需与模式串中的第k个字符再开始比较（主串不需要回溯）。或者换言之,在模式串中第j个字符“失配”时,模式串第k个字符再同主串中对应的失配位置(i)的字符继续进行比较。
需要确定k，我们需要推出next函数
2.赫夫曼树
实现算法：
1.根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F={T1, T2, …, Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，左右子树为空
2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树根结点的权值之和
3.在F中删除这两棵树，同时将新得到的二叉树加入F中
4.重复2, 3，直到F只含一棵树为止
3.DFS
1、任选一顶点作始点 v ，访问该顶点
2、沿深度方向，依次遍历 v 的未访问邻接点——直到本次遍历结束
3、一次遍历完时，若有未访问顶点：任选一个未访问顶点作起始点，GOTO第二步
4.BFS
n所有顶点访问标志visited[]设置为FALSE
n从某顶点v0开始，访问v0，visited[v0]=TRUE，将v0插入队列Q
1.如果队列Q不空，则从队列Q头上取出一个顶点v,否则结束
2.依次找到顶点v的所有相邻顶点v’，如果visited[v’]=FALSE，访问该顶点v’，visited[v’]=TRUE，将v’插入队列Q
3.重复1,2
5.并查集
并查集是一种用来管理元素分组情况的数据结构,并查集可以高效地进行如下操作：
-
查询元素a和元素b是否属于同一组
-
合并元素a和元素b所在组
6.最小生成树
prim
意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。
算法实现：
7.最短路径
Dijkstra
Dijkstra算法采用按路径长度递增的次序产生最短路径
1.设置两个顶点的集合U和T，集合U中存放已找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。
2.初始状态时，集合U中只包含源点，设为v0；
3.然后从集合T中选择到源点v0路径长度最短的顶点u加入到集合U中；
4.集合U中每加入一个新的顶点u都要修改源点v0到集合T中剩余顶点的当前最短路径长度值，集合T中各顶点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过顶点u到达该顶点的路径长度中的较小者。
5.转到3，此过程不断重复，直到集合T中的顶点全部加入到集合U中为止。
8.拓扑排序
如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中, 则该网络中必定不会出现有向环。
9.关键路径