数据结构【DS】图的遍历

BFS

要点

• 需要一个辅助队列
• visited数组，防止重复访问

复杂度

• 
• 时间复杂度：访问结点的时间+访问所有的边的时间
  • 
  • 

广度优先生成树

• 邻接表存储的图的表示方式不唯一，生成树也不唯一

DFS

复杂度

• 
• 时间复杂度：访问结点的时间+访问所有的边的时间
  • 
  • 

深度优先生成树

• 邻接表存储的图的表示方式不唯一，生成树也不唯一

图的遍历和图的连通性

• 无向图：DFS/BFS调用次数 = 连通分量数