生成树是一个无向图 (G) 的子图，它本身是一棵树，包含了图 的所有顶点以及连接图 所需的最少数量的边。它是已知的不含环的边的最大集合。
性质：
- 如果一个图 是不连通的，那么它就不包含生成树（即它拥有许多生成树森林）。
- 如果一个图 有 V 个顶点，那么该图 G 的生成树就有 V-1 条边。
- 在完全图 (Kn) 的情况下，即无向、标记且无权的图，我们可以使用 Cayley 公式来计算可能的生成树数量：Kn = n^(n-2)。
- 对于 K3 图（即 3 个顶点的完全图），可能的生成树数量为 3^(3-2) = 3^1 = 3。
K3 图中可能的生成树
- 除了完全图之外的图，其最小生成树的数量可以使用 Kirchhoff 定理 来求得。
加权有向图中顶点 A 和 E 之间的最短路径 (A, B, D, E)
- 图中任意两个顶点（比如 A 和 E）之间的最短路径，是指该路径中存在的边的权重之和（即 ABDE）在 A 和 E 之间所有可能的路径中是最小的。
- 最短路径可以在有向图、无向图或混合图中找到。
- 寻找最短路径的问题通常可以分为以下几类：
- 单源最短路径： 在这种情况下，计算从一个源顶点到图中存在的所有其他顶点的最短路径。
- 单目标最短路径： 在这种情况下，计算有向图中所有顶点到单个目标顶点的最短路径。这可以通过反转有向图的边来转换为单对最短路径问题。
- 所有顶点对最短路径： 在这种情况下，计算每对顶点之间的最短路径。
最小生成树 (MST) 和最短路径的区别：
最短路径
:—
有一个源点和一个目的地，我们需要找出它们之间的最短路径。
图 不必须是连通的、无向的、带边权重的或标记的。
这里执行边的松弛操作。这里 d(U) 表示源顶点 S 到顶点 U 的距离，其中 C(U, V) 是 U 和 V 之间的距离。如果 d(U) > d(V) + C(U, V)，则 d(U) = d(V) + C(U, V)。例如，20 > 10 + 5，d(U) = 15，这是从源顶点 S 到顶点 U 的最小距离。因此，执行了松弛操作。
如果图是连通的，并且图中存在负权重边环。那么无法计算最短路径，但可以使用 Bellman-Ford 算法检测到负边环。
在图不连通的情况下，位于两个不同分量中的两个顶点之间的距离为无穷大。
基于贪心方法的 Dijkstra 算法和基于动态规划的 Bellman-Ford 算法通常用于寻找单源最短路径。基于动态规划的 Floyd-Warshall 算法用于寻找所有顶点对之间的最短路径。