2022年3月10日月总结博客

最近感觉上学期选了ACM是大有裨益的&＃xff0c;这学期可以秒杀掉数据结构课的练习。

前两次的预选赛&＃xff0c;回来又参加了一次练习&＃xff0c;内容就是把网络预算赛的题挑了几个出来&＃xff0c;并且翻译成了中文的题目&＃xff0c;换成中文之后又能多做出几个来&＃xff0c;比如下面这个&＃xff1a;

 所以就感觉&＃xff0c;能看的懂题目真的很重要&＃xff0c;读题太慢很影响比赛。

这个月基本在看图论&＃xff0c;最大的感悟就是&＃xff0c;图论和并查集联系非常的密切

我从拓扑排序开始看&＃xff0c;先看了拓扑排序&＃xff0c;又看了单源最短路径&＃xff0c;最后看了最小生成树。

拓扑排序&＃xff0c;简单来说&＃xff0c;就是先找到一个入度为0的顶点&＃xff0c;然后将和这个顶点心相连的边全部删除&＃xff0c;再去寻找下一个入度为0的点&＃xff0c;直到得到一个序列。注意图的拓扑排序得到的序列并不唯一。

单源最短路径可以用DFS和Dijkstra算法&＃xff0c;

Dijkstra 算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法&＃xff0c;时间复杂度 O(n2)

要点是每次从未求出最短路径的点中取出距离起点最小路径的点&＃xff0c;以这个点为原点求出距离七点最近的点&＃xff0c;可以用优先队列优化掉nlongn

最小生成树&＃xff0c;主要有两种算法&＃xff0c;Prim算法和Kruskal算法。

前者归并点&＃xff0c;后这归并边

其中Prim算法和Dijkstra算法基本相同

Kruskal算法

选取的边的顶点是不同的连通分量&＃xff0c;且边权值是最小的&＃xff0c;所以我们保证加入的边都不使得非连通图有回路&＃xff0c;且权值也最小。这样最后当所有的连通分量都相同时&＃xff0c;即所有的顶点都在生成树中被连接成功了&＃xff0c;我们构造成的树也就是最小生成树了。相比Prim Dijkstra适合系数图。

接下来打算看二叉树&＃xff0c;打算先从二叉树开始看起。争取半个月学会。