龙空技术网

信息学奥赛大纲(算法篇)

小编程家信奥赛 552

前言:

今天同学们对“图论中的prim算法”大概比较关怀,咱们都想要知道一些“图论中的prim算法”的相关知识。那么小编同时在网络上搜集了一些对于“图论中的prim算法””的相关知识,希望朋友们能喜欢,小伙伴们一起来学习一下吧!

2021年4月2日,中国计算机学会(CCF)发布《全国青少年信息学奥林匹克系列竞赛大纲》。

竞赛分为入门级与提高级两个级别,内容包括:C++程序设计、数据结构、算法、数学等。

本文为《大纲》中的算法清单。

下文中[x]为难度系数。

入门级

基础算法

[1]枚举法

[1]模拟法

[3]贪心法

[3]递推法

[4]递归法

[4]二分法

[4]倍增法

数值处理算法

[4]高精度加法

[4]高精度减法

[4]高精度乘法

[4]求高精度整数除以单精度整数的商和余数

排序算法

[3]冒泡排序

[3]简单选择排序

[3]简单插入排序

图论算法

[4]图的深度优先遍历算法

[4]图的宽度优先遍历算法

[5]洪水填充算法(floodfill)

动态规划

[4]动态规划的基本思路

[4]简单一维动态规划

[5]简单背包类型动态规划

[5]简单区间类型动态规划

提高级

基础算法

[6]分治算法

排序算法

[5]归并排序

[5]快速排序

[6]堆排序

[6]树形选择排序(锦标赛排序)

[5]桶排序

[6]基数排序

字符串算法

[5]字符串匹配算法KMP

搜索算法

[6]搜索的剪枝优化

[6]记忆化搜索

[7]启发式搜索

[7]双向宽度优先搜素

[7]迭代加深搜索

[8]搜索对象的压缩存储

图论算法

[6]Prim和kruskal等求最小生成树算法

[7]求次小生成树算法

[6]Dijkstra、bellman_ford、SPFA等求单源最短路算法

[7]求单源次短路径算法

[6]Floyd-Warshall算法求任意两点间的最短路和传递闭包

[6]有向无环图的拓扑排序算法

[6]求欧拉道路和欧拉回路算法

[6]二分图的构造及其判定算法

[6]最近公共祖先

[7]求强联通分量算法

[7]强连通分量的缩点算法

[7]求割点、割边算法

动态规划

[6]树型动态规划

[7]状态压缩动态规划

[8]动态规划的常用优化

标签: #图论中的prim算法