-
数组与链表
- 一维数组
- 多维数组
- 单向链表
- 双向链表
- 循环链表
-
栈与队列
- 栈（Stack）：LIFO（后进先出）
- 队列（Queue）：FIFO（先进先出）
- 双端队列（Deque）
- 优先队列（Priority Queue）
-
哈希表
- 哈希函数
- 散列冲突处理（开放地址法、链地址法）
-
树
- 二叉树
- 二叉搜索树（BST）
- 平衡树（AVL树、红黑树）
- 堆（最大堆、最小堆）
- 树的遍历（前序、中序、后序、层序）
-
图
- 图的表示（邻接矩阵、邻接表）
- 有向图与无向图
- 权重图与非权重图
- 图的遍历（深度优先搜索DFS、广度优先搜索BFS）
-
递归与分治
- 递归思想
- 分治算法（Divide and Conquer）
- 归并排序
- 快速排序
-
动态规划
- 动态规划思想
- 斐波那契数列
- 背包问题
- 最长公共子序列（LCS）
- 最短路径（Floyd-Warshall算法）
-
贪心算法
- 贪心选择性质
- 活动选择问题
- 哈夫曼编码
-
回溯算法
- 回溯思想
- 八皇后问题
- 全排列
-
排序算法
- 冒泡排序
- 插入排序
- 选择排序
- 归并排序
- 快速排序
- 堆排序
- 桶排序
- 计数排序
- 基数排序
-
搜索算法
- 线性搜索
- 二分搜索
- 深度优先搜索（DFS）
- 广度优先搜索（BFS）
- A* 搜索算法
以下是图算法相关的知识点，涵盖最短路径、最小生成树、拓扑排序和强连通分量的主要内容：
以下是图算法与图分析的知识点：
-
最短路径算法
- Dijkstra算法：用于计算从源点到所有其他节点的最短路径，适用于边权非负的图。
- Bellman-Ford算法：可以处理带负权边的图，能够检测负权环。
- Floyd-Warshall算法：用于计算所有节点对之间的最短路径，适用于稠密图。
-
最小生成树算法
- Kruskal算法：通过选择边的方式构建最小生成树，使用并查集避免环路。
- Prim算法：从一个起始点开始，逐步选择权重最小的边，构建最小生成树。
-
拓扑排序
- 用于有向无环图（DAG），通过入度为0的节点进行排序，可以使用DFS或Kahn算法实现。
-
强连通分量
- Kosaraju算法：通过两次DFS获取图的强连通分量。
- Tarjan算法：单次DFS实现强连通分量，使用栈跟踪访问。
-
网络流算法
- Ford-Fulkerson算法：用于求解最大流问题，基于增广路径。
- Edmonds-Karp算法：Ford-Fulkerson算法的实现，使用BFS寻找增广路径。
-
图的表示
- 邻接矩阵：适用于稠密图，存储所有边的权重，查询快速。
- 邻接表：适用于稀疏图，节省空间，适合遍历。
-
图的遍历
- 深度优先搜索（DFS）：从起点出发，尽可能深的搜索，适合用于图的连通性分析。
- 广度优先搜索（BFS）：从起点出发，逐层访问，适合用于最短路径问题。
-
图的性质
- 连通性：图是否是连通的，分为强连通和弱连通。
- 图的直径：图中任意两点之间的最短路径长度的最大值。
- 图的度数：每个节点的连接边数，影响图的性质和算法性能。
-
图的应用
- 社交网络分析：社交网络中用户之间的连接关系。
- 路径规划：在地图上寻找最短或最佳路径。
- 网络流分析：计算运输网络中的流量最大化问题。
通过掌握图算法与图分析的知识，可以更有效地解决各种实际问题，如优化网络布局、资源分配、路线规划等。
-
时间复杂度
- 大O记法
- 常数时间O(1)
- 线性时间O(n)
- 对数时间O(log n)
- 线性对数时间O(n log n)
- 二次时间O(n^2)
- 指数时间O(2^n)
-
空间复杂度
- 大O记法
- 常数空间O(1)
- 线性空间O(n)
-
递归的时间复杂度分析
- 主定理（Master Theorem）
- 递归树法
- 代入法
-
数据结构的应用
- 栈在表达式求值中的应用
- 队列在广度优先搜索中的应用
- 哈希表在快速查找中的应用
-
排序算法的应用
- 数据排序
- 外部排序
-
图算法的应用
- 网络路由
- 地图导航
-
动态规划的应用
- 最优子结构问题
- 重叠子问题
-
贪心算法的应用
- 最小生成树
- 最优装载问题
-
回溯算法的应用
- 组合问题
- 排列问题
这些知识点构成了算法学习的基础，掌握这些知识能够为解决各种算法问题打下坚实的基础。