数据结构与算法十一:3. 图的遍历

“这是我参与8月更文挑战的第26天，活动详情查看：8月更文挑战”

关注我,以下内容持续更新

数据结构与算法(一):时间复杂度和空间复杂度

数据结构与算法(二):桟

数据结构与算法(三):队列

数据结构与算法(四):单链表

数据结构与算法(五):双向链表

数据结构与算法(六):哈希表

数据结构与算法(七):树

数据结构与算法(八):排序算法

数据结构与算法(九):经典算法面试题

数据结构与算法(十):递归

数据结构与算法(十一):图

图的遍历

图的遍历指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。根据搜索策略的不同,图的遍历方法有深度优先搜索法和广度（宽度）优先搜索法两种算法。广度优先搜索是一层层的遍历,类似于树的层次遍历;深度优先搜索用白话说就是一条道走到黑,走到头再回溯继续往下遍历.例如下图的广度优先搜索顺序是:1、2、3、4、5、6、7、8;深度优先搜索顺序是:1、2、4、8、6、3、7、5。图的存储可以采用邻接矩阵或者邻接表,本文会针对这两种存储结构分别实现深度优先搜索和广度优先搜索。