6.3 图的遍历

6.3.1 广度优先遍历

$n$ 个顶点，$e$ 条边。

邻接矩阵：时间复杂度 $O(n^{2})$

邻接表：时间复杂度 $O(n+e)$

空间复杂度 $O(n)$

LeetCode102 二叉树的层次遍历

广度优先生成树

给定图的邻接矩阵，广度优先生成树是唯一的。邻接表存储不唯一，广度优先生成树不唯一。

6.3.2 深度优先遍历

邻接矩阵：时间复杂度 $O(n^{2})$

邻接表：时间复杂度 $O(n+e)$

空间复杂度 $O(n)$