数据结构之图的遍历
参考网址: https://www.jianshu.com/p/60eb50dbfc39
如果是遍历一个数组,只需要从下标0到下标N-1循环就好了,遍历一个链表只需要从头指针开始直到没有next为止,即使是遍历一棵树,也可以从根结点开始,按照前序、中序和后序等方式进行。之所以可以这样,是因为这些结构都可以找到一个明确的起点,但图不同。如下图所示,有的人希望从A开始遍历,有的人喜欢从C开始...,没有办法规定一个明确的起点。
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210813094256353-1273887079.png)
如果没有策略,遍历一个图就像走迷宫一样,有可能在一个结点停留多次,也可能有几个结点永远不会访问到。而图的遍历,通常有深度优先和广度优先方式,接下来我们就看看这两种方式是怎么做的,有什么区别。
深度优先遍历
深度优先遍历(Depth_First_Search)也称为深度优先搜索,简称为DFS。它是从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。对于非连通图,只需要对它的连通分量分别进行深度优先遍历即可。接下来我们以一个示例演示图的深度优先遍历。如下图所示:
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210813094328637-66134611.png)
在开始进行遍历之前,我们还要准备一个数组,用来记录已经访问过的元素。其中0代表未访问,1代表已访问,如下所示:
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210813094353381-816153439.png)
为了便于演示,假设我们是在走迷宫,A是入口,每次都向右手边前进。首先从A走到B,结果如下:
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210813094534998-242116473.png)
B之后有三个路,我们依然选择最右边,如此下去,直到走到F,如下所示:
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210813094605342-2080144490.png)
到达F后,如果我们继续按照向右走的原则,就会再次访问A,此时我们访问除了A后的最右侧通道,也就是访问G,如下所示:
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210813094641314-1326572864.png)
到达G后,可以发现B和D都走过了,这时候走到H,如下所示:
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210813094702934-861778396.png)
到达H后,可以发现D和E都走过了,也就是说走到了尽头,但是并不代表所有的顶点都访问过了,因为除了最右侧顶点,每个顶点还可能和更多的顶点连通,所以我们从H退回到G,发现全部走过了,再向前退回到F,也全部走过了,直到退回到B时,发现 I 还没走过,于是访问顶点 I,如下所示:
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210813094728832-877433790.png)
同理,访问 I 之后,发现与 I 连通的顶点都访问过了,所以再向前回退,直到回到顶点A,发现全部顶点都访问过了,至此遍历完毕。
广度优先遍历
深度优先遍历可以认为是纵向遍历图,而广度优先遍历(Breadth_First_Search)则是横向进行遍历。还以上图为例,不过为了方便查看,我们把上图调整为如下样式:
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210813094750229-2023380055.png)
我们依然以A为起点,把和A邻接的B和F放在第二层,把和B、F邻接的C、I、G、E放在第三层,剩下的放在第四层。广度优先遍历就是从上到下一层一层进行遍历,这和树的层序遍历很像。我们依然借助一个队列来完成遍历过程,因为和树的层序遍历很像,这里只展示结果,如下所示:
![](https://img2020.cnblogs.com/blog/2173887/202108/2173887-20210813094815416-1269557754.png)
对于非连通图,依然通过visited数组来进行判断即可。
代码实现
图的存储方式有很多种,但是用来实现遍历的思路是一致的,我们以邻接矩阵为例,给出DFS和BFS的参考实现。
深度优先遍历实现
private void DFS(int i) {
// 标记当前元素已经访问
visited[i] = true;
System.out.println("当前访问顶点:" + getVertexByIndex(i));
int next = getFirstNeighbor(i);
while (next != -1) {
if (!visited[next]) {
DFS(next);
}
next = getNextNeighbor(i, next);
}
}
public void DFS() {
for (int i = 0; i < vertexList.size(); i++) {
visited[i] = false;
}
// 非连通图,不同的连通分量要单独进行DFS
for (int i = 0; i < vertexList.size(); i++) {
if (!visited[i]) {
DFS(i);
}
}
}
广度优先遍历实现
private void BFS(int i) {
// 标记当前元素已经访问
visited[i] = true;
System.out.println("当前访问顶点:" + getVertexByIndex(i));
int cur, next;
LinkedList<Integer> queue = new LinkedList<>();
queue.addLast(i);
while (!queue.isEmpty()) {
cur = queue.removeFirst();
next = getFirstNeighbor(cur);
while (next != -1) {
if (!visited[next]) {
// 标记当前元素已经访问
visited[next] = true;
System.out.println("当前访问顶点:" + getVertexByIndex(next));
queue.addLast(next);
}
next = getNextNeighbor(cur, next);
}
}
}
public void BFS() {
for (int i = 0; i < vertexList.size(); i++) {
visited[i] = false;
}
for (int i = 0; i < vertexList.size(); i++) {
if (!visited[i]) {
BFS(i);
}
}
}
完整代码已上传至我的github。
作者:大大纸飞机
链接:https://www.jianshu.com/p/60eb50dbfc39
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- Windows C++遍历所有进程的命令行
- Map集合循环遍历的几种方式
- lintcode二叉树的锯齿形层次遍历 (双端队列)
- oc for in遍历
- Java实现 LeetCode 700 二叉搜索树中的搜索(遍历树)
- Java实现 LeetCode 590 N叉树的后序遍历(遍历树,迭代法)
- 重新整理数据结构与算法(c#系列)—— 树的前中后序遍历[十六]
- 二叉树的前序遍历
- 二叉树的中序遍历
- 使用Javascript递归遍历本地文件夹
- C# 关于XML遍历新增节点,修改属性小例
- 【hiho一下 第十周】后序遍历
- 使用Javascript递归遍历本地文件夹
- 1448. 统计二叉树中好节点的数目-深度优先遍历+最大值传递
- 基于中序遍历找到一个结点的后继结点
- 数据结构——二叉树的遍历
- 数据结构 -- 简单图的实现与遍历 (Java)
- 【数据结构】二叉树的遍历