### ACM/ICPC代码库知识点概述
#### 一、Graph 图论
在计算机科学与信息技术领域，图论作为算法设计的基础部分，具有重要的地位。它不仅涵盖了基础理论知识，还涉及了诸多实际应用问题的解决策略。下面我们将针对文档中提到的一些经典图论算法进行详细介绍。
##### 1. DAG的深度优先搜索标记
- **定义**：DAG（Directed Acyclic Graph，有向无环图）是一种特殊的有向图，其中没有环的存在。
- **应用场景**：在许多场景下，如任务调度、编译器优化等都需要对DAG进行遍历或处理。
- **实现方式**：通过深度优先搜索（DFS）来遍历整个DAG，并对每个访问过的节点进行标记，以便后续的处理或分析。
- **时间复杂度**：O(V+E)，其中V为顶点数，E为边数。
##### 2. 无向图找桥
- **定义**：在无向图中，如果删除某条边会导致图不再连通，则称这条边为“桥”。
- **算法思路**：使用深度优先搜索（DFS）进行遍历，记录每个顶点的发现时间和低值（可以到达的最低发现时间），从而找出所有的桥。
- **时间复杂度**：O(V+E)。
##### 3. 无向图连通度(割)
- **定义**：一个图的连通度是指该图在去除某些顶点或边后仍保持连通所需的最小顶点数或边数。
- **应用场景**：在网络设计、网络安全等领域具有重要意义。
- **算法思路**：可以通过多次深度优先搜索来确定割点或割边。
- **时间复杂度**：O(V+E)。
##### 4. 最大团问题DP+DFS
- **定义**：最大团问题是指在一个图中找到最大的完全子图。
- **算法思路**：采用动态规划结合深度优先搜索的方式，通过枚举子集的方式逐步构建出最大的完全子图。
- **时间复杂度**：较高，但适用于小规模问题。
##### 5. 欧拉路径O(E)
- **定义**：欧拉路径是指一条经过每条边恰好一次的路径。
- **应用场景**：在电路板设计、地图绘制等方面有应用。
- **算法思路**：基于欧拉路径的性质进行构造，即从一个奇度节点出发，通过不断寻找路径来构造最终的欧拉路径。
- **时间复杂度**：O(E)。
##### 6. DIJKSTRA数组实现O（N^2）
- **定义**：DIJKSTRA算法用于计算图中单源最短路径问题。
- **应用场景**：在路径规划、网络路由选择等问题中广泛使用。
- **算法思路**：每次选取距离源点最近的未访问顶点加入到已访问顶点集合中，并更新其他顶点的距离。
- **时间复杂度**：O(N^2)，适用于稠密图。
##### 7. DIJKSTRA O(E*LOGE)
- **定义**：同样用于计算单源最短路径问题，但使用优先队列优化。
- **应用场景**：对于稀疏图更为适用。
- **算法思路**：利用优先队列维护当前未访问顶点中距离源点最近的一个。
- **时间复杂度**：O(ElogE)。
##### 8. BELLMANFORD单源最短路O(VE)
- **定义**：适用于带有负权重边的图。
- **应用场景**：在网络流量控制、物流规划等方面有应用。
- **算法思路**：通过V-1轮松弛操作来更新所有顶点的距离。
- **时间复杂度**：O(VE)。
##### 9. SPFA(SHORTEST PATH FASTER ALGORITHM)
- **定义**：一种改进的贝尔曼-福特算法，用于计算单源最短路径问题。
- **应用场景**：适用于含有负权边的情况。
- **算法思路**：使用队列存储待处理的顶点，并通过不断松弛来更新最短路径。
- **时间复杂度**：平均情况下接近O(E)。
##### 10. 第K短路（DIJKSTRA）
- **定义**：求出从源点到目标点的第k条最短路径。
- **算法思路**：通过多次运行DIJKSTRA算法，每次排除已找到的最短路径，直至找到第k条最短路径。
- **时间复杂度**：较高，取决于k的大小。
##### 11. 第K短路（A*）
- **定义**：与DIJKSTRA类似，但采用启发式方法来加速搜索过程。
- **算法思路**：利用启发函数指导搜索方向，提高搜索效率。
- **时间复杂度**：取决于启发函数的选择。
##### 12. PRIM求MST
- **定义**：PRIM算法用于计算图的最小生成树（Minimum Spanning Tree, MST）。
- **应用场景**：在电路板设计、网络规划等领域广泛应用。
- **算法思路**：从任意一个顶点开始，逐步加入距离当前生成树最近的边。
- **时间复杂度**：O(ElogE)。
##### 13. 次小生成树O(V^2)
- **定义**：求解图的次小生成树，即除了最小生成树之外的第二小生成树。
- **应用场景**：在网络备份路径设计等方面有应用。
- **算法思路**：基于PRIM或KRUSKAL算法基础上，通过修改边权值等方式求解。
- **时间复杂度**：较高，适用于较小规模的问题。
##### 14. 最小生成森林问题(K颗树)O(MLOGM)
- **定义**：在不连通的图中，求解由K个连通分量构成的最小生成森林。
- **应用场景**：在分布式系统、网络管理等方面有应用。
- **算法思路**：基于KRUSKAL算法的思想，使用并查集维护连通分量。
- **时间复杂度**：O(MlogM)。
##### 15. 有向图最小树形图
- **定义**：在有向图中，求解一棵包含所有顶点的最小树形图。
- **应用场景**：在数据通信、资源分配等领域有应用。
- **算法思路**：通常基于DAG进行处理，利用拓扑排序等手段。
- **时间复杂度**：取决于具体实现方法。
##### 16. MINIMAL STEINERTREE
- **定义**：求解最小Steiner树，即在给定点集中加入额外的Steiner点以构建一棵最小生成树。
- **应用场景**：在电路板设计、网络规划等方面有应用。
- **算法思路**：通常基于动态规划的方法，通过递归构建最小Steiner树。
- **时间复杂度**：较高，适用于小规模问题。
##### 17. TARJAN强连通分量
- **定义**：TARJAN算法用于计算有向图中的强连通分量。
- **应用场景**：在网络分析、软件工程等领域有应用。
- **算法思路**：利用深度优先搜索进行递归处理，通过维护低值来识别强连通分量。
- **时间复杂度**：O(V+E)。
##### 18. 弦图判断
- **定义**：弦图是一种特殊类型的图，具有良好的性质。
- **应用场景**：在优化问题、算法设计等领域有应用。
- **算法思路**：通过检查是否存在三角形和四边形等条件来判断是否为弦图。
- **时间复杂度**：较低。
##### 19. 弦图的PERFECT ELIMINATION点排列
- **定义**：在弦图中寻找一种顶点排列方式，使得每次删除一个顶点及其相邻顶点后形成的图仍然为弦图。
- **应用场景**：在算法设计、图着色等方面有应用。
- **算法思路**：利用深度优先搜索等方式进行寻找。
- **时间复杂度**：取决于具体实现方法。
##### 20. 稳定婚姻问题O(N^2)
- **定义**：求解一个稳定的婚姻匹配方案，使得每对夫妇的匹配都是稳定的。
- **应用场景**：在资源分配、人员匹配等领域有应用。
- **算法思路**：采用GALE-SHAPLEY算法进行匹配，通过不断提出建议直到达成稳定匹配。
- **时间复杂度**：O(N^2)。
##### 21. 拓扑排序
- **定义**：对一个有向无环图进行排序，使得所有有向边均指向排序的前方。
- **应用场景**：在任务调度、编译器优化等方面有应用。
- **算法思路**：利用入度为0的顶点进行排序。
- **时间复杂度**：O(V+E)。
以上内容涵盖了图论中的一些经典算法及其实现方法。这些算法不仅理论意义重大，而且在实际应用中也具有广泛的用途。掌握这些算法不仅可以帮助我们更好地理解图论的基本概念，还能为解决实际问题提供强有力的工具支持。
