关于数据结构和图论的一些入门攻略

古城微笑少年丶 2022-06-10 06:49 74阅读 0赞

我是负责我们队数据结构和图论的，在集训队做了一个多月的题，应该算是图论和数据结构入门了吧，这里我推荐一些图论和数据结构的算法学习顺序（我的见解），如果对这一方面有兴趣的可以看一看。（日常菜的抠脚不想去刷题）  
首先，相比数据结构，图论入门要简单一些，要入门图论，先要学会dfs和bfs，题目的话每一样入门题10道，中档题10道，难题5,6道就差不多懂了，dfs就是要学习回溯和强枝剪的思想，有时候好的dfs+强剪枝是可以媲美dp的。bfs呢就是要活用结构体，输出路径，难度高一些的有手写队列，双向bfs，加上一些状态压缩搜索什么的，我的博客的题解顺序也是按难度来的。学完这些你还只是有了图论的一些工具，这时你可以学习拓扑排序，无向欧拉路判定什么的，这些还是比较简单，一般用一些模拟+dfs或者bfs就能做出来，后面混合图（无向和有向）难度就很高了，需要大量的图论理论知识qaq就不用做了（我还不是很会），如果是入门到这里就可以了。  
然后可以正式入手图论了，首先是最短路径算法，有Floyd（三重暴力），迪杰斯特拉算法（单源最短路，最常用），贝尔曼弗德(求负权值最常用的算法)，SPFA（单源最短路，bfs的思想，有时有奇效），这些算法每一个都像模板一样，每个做个10题左右就差不多了。然后就可以学最小生成树，有克鲁斯卡尔算法（贪心，也是最常用算法），prim算法（适合边很多的稠密图），注意，图论经常和一些stl中的东西搭配，这个学习的过程中也要学很多stl的用法，比如最基础的sort对结构体排序，优先队列的使用，vector和map的用法等等，我的博客有总结的（总结向里面），最小生成树也差不多每种算法做个10题总结下模板就好了，然后就可以做二分匹配的了，也是模板，有匈牙利算法，HK算法（只做过一题），KM算法（完全不会），匈牙利做算法是最常见的算法，邻接矩阵的做法会比邻接表的更慢，所以邻接表写法要会，然后如果邻接表的匈牙利算法都TLE了那么就一定是用HK算法了。。这个有的复杂，准备好模板就好了，然后总之，匈牙利算法是用于求最大匹配数的（只要按要求能匹配就行的那种），而KM算法是用来求带权值的最大匹配数的（就是符合条件的最佳选择），到这就差不多图论入门了吧（写完这篇博客就要去学KM和KMP，最大最小流之类的了qaq好难啊）  
然后数据结构方面，首先从简单的并查集开始，学会路径压缩就差不多了，做个10题左右吧（根据并查集好像是图论的，不过没差了），然后就开始痛并快乐的线段树之旅了（当你不看题解做出一题来都很爽hhhhh），线段树首先就是做什么操作格子和敌兵布阵吧，也就是线段树的单点更新题，这个就差不多是个模板，一开始看不懂不要着急，多做几题就觉得很水了，差不多做了5题之后就可以升级了，线段树的区间更新和区间查询，恩恩，是不是感觉难一些了，做个5题左右，就做线段树的区间合并吧，还有学会区间更新的lazy tag思想，这对很多搞数据结构的是一个巨大的坎，我差不多被lazy tag和区间合并虐了一个星期才搞明白是怎么回事，学会这些就算是线段树入门了，中档一些的有线段树的离线操作，说白了就是在区间更新或者查询的时候做一些手脚，也比较好理解，然后高级一点的就是学会离散化。。这个在线段树里面很常用也很好用，既可以省时间又可以省空间，被虐几次就可以做扫描线了，扫描线我也是一题就做一天的那种。。。被虐多了就好了，习惯就好，最后最恐怖的就是二维线段树qaq，一开始完全不会做（现在也基本是套模板，不是很理解），被虐个一天就似懂非懂了，昨天终于AK了线段树专题好爽啊hhhhhhh。  
对了忘记说了，做线段树的区间更新之前，可以做树状数组的题了。。。虽然能用树状数组做的题用线段树基本都能做，用线段树能做的树状数组不一定能做，但真的是好用！！！对于一些大数据的题目，我们有时开线段树就要很多的内存，如果题目只是单点更新，区间查询，我们就可以用树状数组来实现，树状数组不仅代码量很短，耗的内存是线段树的四分之一，而且速度也要比线段树快一些，抢一血的必备数据结构，其实树状数组也可以实现区间更新，这个在博客题集里面有，可以区间更新+单点查询，总之，这是个很强的数据结构，也是必备的，做个10题左右就差不多了，然后一些难的有分情况一次性开10棵树状数组和二维树状数组那种题目，做过就好了，难以理解是肯定的。

这个同时，你的stl也要跟上，数据结构经常伴随着二分查找的操作，还有离散化的时候经常用unique这个函数，vector也常用于建树来转成线段树，所以这些也要会的。

好了，总结就到这里，又要回到（tong）快（ku）乐的刷题之路了