最近数据结构学到了图这一块，相比于之前，这块的知识太TMD的难了，自己看书前后翻好几遍都看不明白。看了几期视频之后感觉有些明白了，这类算法还是结合视频比较好理解，主要是一个动态变化的过程，看明白这个过程，再去看代码就清晰多了，这里把几期视频集中一下，做个备忘。
1. 深度优先遍历（DFS）
1.1 讲解
图的遍历就是按照一种顺序，访问全部顶点的过程。
这里以邻接矩阵作为存储结构说明深度优先遍历。邻接矩阵的每一行说明了该行所对应顶点与其他顶点的连接情况。
DFS.1
以图DFS.1为例，首先取出第0行，{0, 1, 0, 1, 1, 0, 0, 0}，其中的1说明
V0与V1，V3和V4有边的连接。深度优先搜索即按照这一从左到右的排列顺序，遇到有连接的边就顺着这个边往下走，而暂时不再搜索该顶点所连接的其他边。
同样以图DFS.1为例，使用如下代码
for (j = 0; j < G.numVertexes; j++)
{
if (G.arc[i][j] == 1 && !visited[j])
DFS(G, j);
}
从左到右在{0, 1, 0, 1, 1, 0, 0, 0}中找到第一个与V0有联系的顶点，在这里就是V1，找到后就暂时暂停循环，也就是不再往下找V3和V4，而是顺着第一条边走到V1，走到V1后执行标记、打印操作。
接下来就是一样的了，以V1为关注点，即取出第1行，从左到右在{1, 0, 1, 0, 1, 0, 0, 0}找到第一个与V1有联系的顶点，这里看到是V0，但是V0已经访问过，因此跳过不予考虑，继续往右找到有联系但没有访问过的顶点，也就是V2。
同样的方法走到V5，从左到右在{0, 0, 0, 1, 0, 0, 0, 0}中寻找未访问且有联系的点，发现没有。于是返回到V2，从刚才暂停的点往后寻找第二个有连接且未访问的点，发现没了。返回到V1，发现V4，于是顺着这条边往下走......
基本流程就是找到从左到右找到有连接且未访问的下级顶点，只要能找到就一直往下走；直到找不到就返回一级（一级不行就两级、三级...），返回到能找到的点再往下走；直到所有顶点全部访问，遍历完毕
所谓深度优先就是一直往下走，不撞南墙不回头🐶
1.2 动画演示
DFS.gif
视频：（小甲鱼）数据结构和算法--P60深度优先遍历
1.3 代码
邻接矩阵：Graph/DFS_Adjacent_Matrix.c
邻接表：Graph/DFS_Adjacency_List.c
2. 广度优先遍历（BFS）
2.1 讲解
对于图，从一个点开始，可以根据其他顶点与该顶点的远近，形成不同的层，与该顶点直接的相连的就是第一层，隔一个顶点的是第二层...以此类推，如下图所示。
图的分层
按照层级顺序，从左到右从上到下依次遍历：
- 第一层：A
- 第二层：B F
- 第三层：C I G E
-
......
知道了遍历顺序，如何实现呢？答案是队列！
如下图所示：
队列实现BFS
具体过程
首先选择初始顶点，入队
顶点出队→查找有联系且没有访问的下级顶点→打印下级顶点→下级顶点入队
同样以邻接矩阵为例，说明具体过程：
因为初始化从A开始，进入循环后A出队，返回顶点A在邻接矩阵的行数，从邻接矩阵G中取出这一行{0, 1, 0, 0, 0, 1, 0, 0, 0}遍历这一行，找出为1且没有访问过的顶点，也就是与A有连接且没有访问过的顶点，可以看出是B和F，然后标记为已访问、打印、入队，完成一次循环。
通过队列这一数据结构可以保证从上往下，从左到右的顺序。具体过程视频里讲的更清楚，可以看视频。
2.2 视频
哔哩哔哩[Python] BFS和DFS算法（第1讲）
2.3 代码
邻接矩阵BFS：Graph/BFS_Adjacent_Matrix.c
邻接表BFS：Graph/BFS_Adjacency_List.c
网友评论