图--遍历（深度优先）

之前章节我们分别学习了邻接矩阵、图的基本术语、邻接表，十字链表，本节接着学习图的遍历方式：深度优先遍历

$\bullet$ 概念

从某顶点开始，依次向下（邻接点的邻接点）访问其邻接点直到每个顶点都被访问依次，深度优先遍历，又称深度优先搜索，简称DFS（约等于树的前序遍历）

$\bullet$ 图示

（如图红色的线即数字表示从顶点A出发依次查找的路径，当走完路径5时在D点，对于D的邻接点有A、E，但是AE均已被访问，故原路退回，直到框红的位置F ；对于非连通图，只需要对其连通分量分别进行深度优先遍历，即：若图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点进行DFS ）

$\bullet$ JavaScript代码实现

$\alpha$ 邻接矩阵

$\ast$ 构建邻接矩阵

1-使用vexs作为顶点表记录各个顶点

2-根据顶点数N，初始化一个N*N的邻接矩阵

3-根据邻接边构建邻接关系

$\ast$ 创建辅助对象visited，标记每一个顶点位置为false表示未被访问过

$\ast$ 双for过程中找矩阵中不为0的顶点且未在辅助对象中被标识为true，满足时，以当前顶点为起始点继续向下访问

$\ast$ 时间复杂度为： $（n^2）$

$\beta$ 邻接表

$\ast$ 构建邻接表

1-定义顶点表和单链表的节点类型

2-初始化顶点表，其指针域first初始为空，数据域data值为顶点

3-根据边数遍历，使用头插法创建单链表

I-找到一条边上两点在顶点表的位置

II-将新节点插入到单链表表头，使其next指向原表头节点

III-无向图中还需要创建当前节点邻接的节点

$\ast$ 创建visited对象，记录顶点是否已被访问过

$\ast$ 递归访问