数据结构学习，图的遍历（DFS和BFS）

前言

前面我们学习了数据结构图的基础，关于图的定义，图的术语，以及对图结构使用邻接矩阵和邻接表的存储处理，今天我们学习图的遍历，我们主要学习DFS（深度优先遍历）和BFS（广度优先遍历）两种遍历。这两种遍历衍生的搜索在算法里面考的比较多，在一些算法比赛也运用的比较频繁，像蓝桥杯这样的比赛老喜欢考了，考BFS搜索和DFS搜索。好了别的咋不扯了，我们开始学习吧！！

每日一遍，防止恋爱

1.图的遍历

图的遍历指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。由于图结构本身的复杂性，所以图的遍历操作也较复杂，我们一般是给定一个图G=(V,E)和其中的任一顶点v，从顶点v出发，访问图G中的所有顶点而且每个顶点仅被访问一次。为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。

1.DFS

深度优先遍历（Depth First Search，简称DFS）

1.访问顶点v----》2.选择一个与顶点v相邻且没被访问过的顶点w，从w出发深度优先遍历----》直到图中与v相邻的所有顶点都被访问过为止。（讲人话：就是递归，一直往下面找自己没有遍历过的值，直到到了最后一层，而且这一层为空，就返回到上一层，在上一层找其他相邻的值遍历往下遍历）（就是二叉树的先根遍历