第六章 图的遍历

基础概念

相关提炼内容见 graph。

广度优先搜索 Breadth-First-Search, BFS

• 伪代码
• BFS 算法的性能分析
  • 空间复杂度$O(|V|)$
  • 采用邻接表时间复杂度$O(|V|+|E|)$
  • 采用邻接矩阵的时间复杂度为$O(|V{|}^2)$
• BFS 算法求解单源最短路径问题
• 广度优先生成树

深度优先搜索 Depth-First-Search, DFS

• 伪代码
• DFS 算法的性能分析
  • 空间复杂度$O(|V|)$
  • 采用邻接表的时间复杂度$O(V+E)$
  • 采用邻接矩阵时间复杂度$O(|V{|}^2)$
• 深度优先的生成树和生成森林

图的遍历与图的连通性