图论算法与数据结构：Dijkstra、Prim、最小生成树与网络流

"常用算法代码" 本资源是一份包含多种常用算法的代码库，主要涵盖图论、网络流和数据结构等多个领域，适用于ACM/ICPC等编程竞赛或算法学习。以下是部分算法的详细说明： ### 图论 1. **DAG的深度优先搜索标记**：在有向无环图(DAG)中，深度优先搜索(DFS)常用于标记节点的访问状态，例如判断环、找出最长路径等。 2. **无向图找桥**：桥是指在无向图中，如果移除该边会导致图产生多个连通分量的边。寻找桥的方法通常基于Tarjan或Kosaraju的算法。 3. **无向图连通度(割)**：计算图的连通分支，即最小割的数量，可以使用DFS或BFS来实现。 4. **最大团问题**：寻找图中最大的完全子图，可采用动态规划(DP)结合DFS解决。 5. **欧拉路径**：找到一个图中的欧拉路径，即从一个顶点出发经过每条边恰好一次返回原点的路径，时间复杂度为O(E)，其中E是边的数量。 6. **Dijkstra算法**：求解单源最短路径问题，有数组实现O(N^2)和优化后的O(E*logE)两种版本。 7. **Bellman-Ford算法**：处理含有负权边的单源最短路径问题，时间复杂度为O(VE)。 8. **SPFA算法**：一种基于队列的优化Dijkstra算法，用于处理带负权边的情况。 9. **第K短路**：找到起点到其他点的第K短路径，可以用Dijkstra或A*算法进行扩展。 10. **A*算法**：启发式搜索算法，结合了Dijkstra的最优性和A函数的启发式信息，用于更快地找到目标路径。 ### 网络流 1. **二分图匹配**：寻找二分图中最大匹配，有DFS和BFS两种实现方式，以及Hopcroft-Carp和Kuhn-Munkres算法。 2. **最小割**：在无向图中找到最小割，解决分配问题，如匈牙利算法。 3. **最大流**：通过Dinic或 HLPP算法寻找网络中最大流量，最小费用流则考虑了路径上的费用。 ### 数据结构 1. **树状数组**：高效处理区间查询和更新的数据结构，常用于求和、统计等问题。 这份代码库还包含了其他算法，如拓扑排序、有向图的强连通分量、最小生成森林、最小树形图、最小Steiner树、弦图判断与消除、稳定婚姻问题的解决方案等。这些算法对于理解和解决实际问题具有很高的价值，适合计算机科学与技术领域的学习者和从业者参考。