6. 【图的应用1】最⼩⽣成树（Prim、kruskal）、最短路径（BFS、Dijkstra、Floyd{含有快速求解}）

文章目录

• 最⼩⽣成树（最⼩代价树）
• • 1. Prim 算法（普⾥姆）【做题步骤】
  • • 1.1时间复杂度：O(|V|^2) 适合⽤于边稠密图
  • 2. Kruskal 算法（克鲁斯卡尔）【做题步骤】
  • • 2.1 时间复杂度：O( |E| * log2|E| ) 适合⽤于边稀疏图
• 最短路径问题
• • 1. BFS算法（只用于：无权图）
  • 2. Dijkstra（迪杰斯特拉）算法:（用于：带权图、无权图）【权值必须为正】
  • 3. Floyd（弗洛伊德）算法：（用于：带权图、无权图）【允许图中有负值权，但不允许含负值权的边有回路】