图的遍历
遍历的定义
遍历实质:找每个顶点的邻接点的过程.
图的特点
图可能存在回路所以我们需要设置辅助数组来标记访问过的节点,防止多次访问.
遍历方法
深度优先搜索(DFS)
方法:
深度优先遍历可能有很多种方式
连通图的深度优先遍历类似于树的先根遍历.
邻接矩阵的深度优先遍历
DFS结果
2->1->3->5->4->6
算法实现
邻接表的深度优先搜索
DFS算法效率分析
结论:
稠密图适合在邻接矩阵上进行深度遍历
稀疏图适合在邻接表上进行深度遍历
遍历实质:找每个顶点的邻接点的过程.
图可能存在回路所以我们需要设置辅助数组来标记访问过的节点,防止多次访问.
方法:
深度优先遍历可能有很多种方式
连通图的深度优先遍历类似于树的先根遍历.
DFS结果
2->1->3->5->4->6
DFS算法效率分析
结论:
稠密图适合在邻接矩阵上进行深度遍历
稀疏图适合在邻接表上进行深度遍历