什么是拓扑排序？

拓扑排序是对 有向无环图 (Directed Acyclic Graph, DAG) 的顶点进行的一种线性排序。该排序满足这样的条件：对于图中任意一条有向边 (u, v)，顶点 u 在排序中都出现在顶点 v 的前面。

简单来说，拓扑排序就是一种能把图“拉直”成一条线性的序列，并保证所有的依赖关系（边的方向）都得到满足的排序方式。一个有向图能进行拓扑排序的 充要条件 是它是一个 DAG。

什么是最小生成树 (MST)？

在一个 无向连通图 中，一个 生成树 是图的一个子图，它包含了图中所有的顶点，并且是一棵树（即，没有环）。一个图可以有多个生成树。

最小生成树 (Minimum Spanning Tree, MST) 是指在一个带权的无向连通图中，所有生成树里，边的权重之和最小的那一棵。

Kruskal 算法的核心思想

Kruskal 算法是一种基于 贪心策略 的最小生成树算法。它的思想非常直观和简单：

什么是 Floyd-Warshall 算法？

Floyd-Warshall 算法（简称 Floyd 算法）是一种用于计算 所有顶点对之间最短路径 的算法。与 Dijkstra 和 SPFA 不同，它不是单源最短路算法，而是一次性计算出图中任意两点之间的最短距离。

Floyd 算法可以正确处理带有 负权边 的图，但不能处理带有 负环 的图。它非常适合用于稠密图。

核心思想：动态规划

Floyd 算法的本质是一个动态规划。我们定义一个二维数组 dp[k][i][j]，表示从顶点 i 到顶点 j，只允许经过编号从 1 到 k 的顶点作为中间点时，所能得到的最短路径长度。

什么是 SPFA 算法？

SPFA（Shortest Path Faster Algorithm）是一种用于计算单源最短路径的算法。与 Dijkstra 算法不同，SPFA 可以处理带有 负权边 的图。它实际上是 Bellman-Ford 算法的一种队列优化版本。

核心思想

SPFA 算法的核心思想是 动态逼近。它维护一个队列，队列中存放着“刚刚被成功松弛过”的顶点。只有当一个顶点的距离 dist[u] 变小时，它才有可能去更新它的邻居 v 的距离 dist[v]。因此，只有那些距离值变小的顶点，才需要被放入队列中，作为下一轮松弛操作的出发点。

什么是二分图最大匹配？

• 二分图: 一个图的顶点可以被分为两个独立的集合 U 和 V，使得所有的边都连接 U 和 V 中的顶点，而 U 或 V 内部没有边。
• 匹配: 图中的一个边的集合，其中任意两条边都没有公共的顶点。
• 最大匹配: 一个图中，包含边数最多的匹配。