数据结构与算法的学习内容包括图的各种遍历方法及其实际应用场景

一、图的遍历

图的遍历说明: 从一个给定的连通图中的任意一个起始顶点出发，在某些边上系统地访问该图中的所有顶点，并确保每个顶点只被访问一次。

遍历实质: 找每个顶点的邻接点的过程

图的特点: 图中可能存在环, 且图中的任一节点都可能与其它节点连通，在遍历完某个节点之后可能会沿着某些边又回到了先前已经访问过的节点

为避免重复访问:

解决思路: 通过设置辅助阵列visited[n]来标记每个被访问过的顶点。在初始状态下, 所有顶点的初始状态均为visited[i]=0.当一个顶点i被访问时, 我们将其visited[i]设为1, 以便避免重复访问同一个顶点.

1.深度优先搜索遍历(类似于树的先根遍历)

1) 深度优先搜索遍历方法:

从起始顶点v出发进行访问

依次遍历其所有邻接顶点w₁

然后转向与w₁相邻未被访问过的任一节点w₂

继续这一探索流程
...
一直到所有与之相连的节点都被彻底探索完毕为止
接着返回至最近一次被完全处理的节点位置上
检查是否存在尚未被覆盖的相邻节点
如果有，则进入该子节点展开类似的遍历操作
否则就退回到前一步骤进行搜索
重复上述操作直至连通图中的每一个节点都被成功覆盖

![](https://cdl.itadn.co