图论算法概述

liweiwei1419 ... 2021-12-15 图论
  • Dijkstra
  • 最小生成树
About 1 min

# 参考资料

  • 《算法(第 4 版)》
  • 《算法导论》

# 「最短路径问题」知识点

「最短路径问题」专题要解决的问题和重点:

  1. 单源最短路径问题(Dijkstra 算法、Bellman-Ford 算法)
  2. 所有点对的最短路径问题(Floyd 算法)。

提示

本专栏只讲解 Dijkstra 算法和「松弛操作」。

# 单源最短路径问题

  1. Dijkstra 算法(没有负权边的单源最短路径问题,重点讲解)
  • 松弛操作:重点强调由于没有负权边,因此每一轮可以确定从源点到一个顶点的最短路径
  • 算法思想:贪心算法、动态规划
  • 数据结构:堆(优先队列)
  • 时间复杂度
  1. Bellman-Ford 算法(有负权边的单源最短路径问题)
  • 算法思想:动态规划
  • 需要讲清楚进行顶点个数 - 1 次操作是找到最短路径的上限,并且最后还要执行一次松弛操作判断是否有负权环
  • SPFA 算法的思想可以提一下,甚至可以不讲,面试肯定不会考
  • 时间复杂度

# 所有点对的最短路径问题

Floyd 算法其实还是松弛操作和动态规划。

# 「最小生成树」知识点

「最小生成树」专题要解决的问题:

找到无向图的最小生成树。

# 切分定理

Kruskal 算法和 Prim 算法都利用到了「切分定理」。

# Kruskal 算法

  • 算法思想:贪心算法
  • 数据结构:并查集

# Prim 算法

  • 算法思想:贪心算法
  • 数据结构:堆(优先队列)
Last update: January 14, 2022 10:18
Contributors: liweiwei1419 , suanfa8