2024-12-14 日报 Day16

今日的鸡汤

成年人的生活,万般皆苦,唯有自渡,
活着就要遇山开山,见水架桥,
其实一直陪着你的永远都是那个了不起
的自己。

今日学习内容

1、《JavaScript数据结构与算法》 P167-169

今日笔记

1、图的遍历
和树数据结构类似，图的遍历也有两种算法：广度优先搜索（BFS）和深度优先搜索（DFS）。图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径、检查图是否连通、检查图是否含有环等。
图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探
索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。
广度优先搜索算法和深度优先搜索算法基本上是相同的，只有一点不同，那就是待访问顶点
列表的数据结构。

算法	数据结构	描述
深度优先搜索	栈	通过将顶点存入栈中（在第3章中学习过），顶点是沿着路径被探索的，存在新的相邻顶点就去访问
广度优先搜索	队列	通过将顶点存入队列中（在第4章中学习过），最先入队列的顶点先被探索

当要标注已经访问过的顶点时，我们用三种颜色来反映它们的状态。

 白色：表示该顶点还没有被访问。

 灰色：表示该顶点被访问过，但并未被探索过。

 黑色：表示该顶点被访问过且被完全探索过。
2、广度优先搜索
广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。
3、深度优先搜索
深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶
点被访问了，接着原路回退并探索下一条路径。