导语：最近在刷牛客，在做了一些题目之后，整理了一些思路非常好的算法，在此做些记录，当然仅仅是算法的思路，因为我个人觉得学习算法，更多的是去掌握不同算法的思路及特性，而代码只是实现他的工具，在此希望能够帮助大家，同时如果某些概念或者用词不准确，欢迎指正！（ps：将题目或者业务需求进行数据结构化真的是一件非常重要的事）

一、DFS（深度优先搜索）--剪枝思想--回溯算法

此类算法的核心思想在于不断的递归，再通过剪枝（剪枝思想百度即可），形成方法回溯，比如在1-9中，找到几个数和为5，而从1出发，加到3之后，数值6已经超过5了，那说明后面的6-9已经没有必要再去加了，此时可以增加一个剪枝判断，进行回溯，缩短查询的路径。时间复杂度：点数v，边数e，邻接矩阵:O(v²)    邻接表:O(e+v)

二、BFS（广度优先搜索）

它的基本思想是从一个顶点开始，辐射状地优先遍历其周围较广的区域。例如从起始顶点top出发，依次访问top的各个未被访问过的邻接顶点p1,p2...pn，然后再依次访问p1,p2...pn的所有未被访问过的邻接顶点，再从这些访问过的顶点出发，再访问它们所有未被访问过的邻接顶点….以此类推，直到途中所有的顶点都被访问过为止。这个算法和DFS都是穷举算法，在于去尝试所有的路径，找到符合要求的路径。时间复杂度：点数v，边数e，邻接矩阵:O(v²)    邻接表:O(e+v)

三、prim算法（普里姆算法）与Kruskal算法（克鲁斯卡尔算法）

1、prim算法是用于求最小生成树的算法，思想就是，从任意一个顶点开始，选择与当前顶点集最近的一个点，并将两点之间的边加入到树中（也就是我们要的数据路径）。Prim算法在找当前最近顶点时使用到了贪婪算法。时间复杂度：这里记定点数v，边数e，邻接矩阵:O(v²)    邻接表:O(elog₂v)

2、Kruskal算法是将所有的边进行排序，然后从最小的边开始遍历，如果在点的集合中没有这两个点，则将该边加入到加过集中，并且将两个点加入已被选择的集合。时间复杂度：elog₂e  e为图中的边数

这两个算法思想比较简单，但是实现起来有点麻烦，具体的可以去我参考的网址查看：https://blog.csdn.net/gettogetto/article/details/53216951