之前章节我们分别学习了邻接矩阵、图的基本术语、邻接表,十字链表,本节接着学习图的遍历方式:深度优先遍历
概念
从某顶点开始,依次向下(邻接点的邻接点)访问其邻接点直到每个顶点都被访问依次,深度优先遍历,又称深度优先搜索,简称DFS(约等于树的前序遍历)
图示
JavaScript代码实现
邻接矩阵
构建邻接矩阵
1-使用vexs作为顶点表记录各个顶点
2-根据顶点数N,初始化一个N*N的邻接矩阵
3-根据邻接边构建邻接关系
创建辅助对象visited,标记每一个顶点位置为false表示未被访问过
双for过程中找矩阵中不为0的顶点且未在辅助对象中被标识为true,满足时,以当前顶点为起始点继续向下访问
时间复杂度为:
邻接表
构建邻接表
1-定义顶点表和单链表的节点类型
2-初始化顶点表,其指针域first初始为空,数据域data值为顶点
3-根据边数遍历,使用头插法创建单链表
I-找到一条边上两点在顶点表的位置
II-将新节点插入到单链表表头,使其next指向原表头节点
III-无向图中还需要创建当前节点邻接的节点
创建visited对象,记录顶点是否已被访问过
递归访问