您的位置: 首页 > 文章 > 数据结构——树（知识总结） 数据结构——树（知识总结） 分类: 文章 • 2025-02-02 18:43:40 文章目录 图的应用 最小生成树 普里姆（prim）算法 克鲁斯卡尔(Kruskal)算法 最短路径 迪杰斯特拉（Dijkstra）算法 弗洛伊德（Floyd）算法 图的应用 最小生成树 普里姆（prim）算法 克鲁斯卡尔(Kruskal)算法 prim算法时间复杂度为O（n^2）,克鲁斯卡尔算法时间复杂度为O（eloge）。对于两个算法，克鲁斯卡尔算法对于稀疏图优势大，而普里姆算法对于稠密图更好一点。 最短路径 迪杰斯特拉（Dijkstra）算法 问题抽象：在有向网中A点到达B点的多条路径中，寻找一条各边权值之和最小的路径，即最短路径 弗洛伊德（Floyd）算法 两种算法的时间复杂度都是O（n^3）,对有向图和无向图都适用。
prim算法时间复杂度为O（n^2）,克鲁斯卡尔算法时间复杂度为O（eloge）。对于两个算法，克鲁斯卡尔算法对于稀疏图优势大，而普里姆算法对于稠密图更好一点。
