图的算法

文章发布时间:

2024-04-08

最后更新时间:

2026-08-29

文章总字数:

87

预计阅读时间:

1 分钟

克鲁斯卡尔（Kruskal）
适用于边稀疏的连通网络。
$O(e*log_2e)$
普利姆（Prime）

适用于边稠密的连通网络。
$O(n^2)$

最小生成树、贪心算法

迪杰斯特拉（Dijstra）
$O(n^2)$
贝尔曼-福特（Bellman-Ford）
$O(n^3)/O(n^2+n*e)$
弗洛伊德（Floyd）
$O(n^3)$

最短路径、动态规划