文档章节

图的遍历——深度优先搜索(Depth First Search)

啊哈关关
 啊哈关关
发布于 2018/01/20 09:50
字数 1236
阅读 1302
收藏 0

1.深度优先搜索(Depth First Search)遍历类似于树的先根遍历,是树的先根遍历的推广。

假设初始状态是图中所有的顶点未曾被访问,则深度优先搜索可从图中某个顶点V出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,相当于一个递归的过程,直到图中所有和v有路径相通的顶点都被访问到;

若此时图中还有顶点未被访问,则选图中的一个未曾被访问的顶点做起始点,重复上述过程,直至图中所有顶点都被访问到为止。

2.以下图为例,做个简单的深度优先搜索遍历过程:

该图有v1,v2...到V9共9个顶点,假设从顶点V1开始出发进行搜索遍历,在访问了V1顶点之后,选择邻接点V2,因为V2未曾被访问,则以V2为起始点,进行深度优先搜索,(类似于迭代),此时V2的邻接点有3个,分别为V1,V4,V5,V2,选择未被访问的邻接点V4,然后会以V4为起始点,进行深度优先搜索,此时V4的邻接点为V2和V8,V2已经被访问,顶点V4选择未曾被访问的顶点V8,这时会以V8为起始点做优先搜索遍历,V8的邻接点是V4和V5,而V4已经被访问,所以V8选择未曾被访问的顶点V5,V5的邻接点都被访问了,则回到V8,V8的所有邻接点也被访问了,回到V4,v2,到达V1,此时V1会选择未被访问的顶点V3,然后会以V3为起始点进行深度优先搜索,V3会选择V6,然后以V6为起始顶点做深度优先搜索,V6选择未被访问的邻接点V9,而V9会选择未被访问的V7,然后以V7为起始点做深度优先搜索遍历,发现V7的邻接点都已被访问,则回到V9,V9的邻接点也已被访问 ,则回到V6,回到V3,V1,此时发现V1的邻接点已经全部被访问。而且图中其他顶点也已经被访问,所有的顶点都已经被访问,说明这次的深度有限搜素遍历已经全部完成。

由此得到的顶点访问的顺序为:

V1->V2->V4->V8->V5->V3->V6->V9->V7

3.很显然,上述遍历的过程是一个递归的过程。为了在遍历中区分顶点是否已经被遍历,需要附设访问标志数组visited[0..n-1],n是指顶点的个数,其初值为false.一旦某个顶点被访问,其相应的分量值为true,visited[i]=true.

4.代码附上:采用的是以邻接表的存储结构

   /**
     * 从第i个顶点出发递归深度优先遍历图
     * @param i
     * @param visited
     */
    public void DFS(int i, boolean[] visited) {
        VNode v = mVexs[i];
        visited[i] = true;
        ENode node= v.firstEdge;
        System.out.println(i+"("+mVexs[i].data+")");
        while(node!=null){
            if(!visited[node.ivex]){
                DFS(node.ivex,visited);
            }
            node=node.nextEdge;
        }
    }

    public void DFS() {
        boolean[] visisted = new boolean[mVexs.length]; //创建一个以顶点数为容量长度的布尔数组用来存取顶点数是否被访问的标志
        //初始化顶点标志数组
        for (int i = 0; i < mVexs.length; i++) {
            visisted[i] = false;
        }
        for (int i = 0; i < mVexs.length; i++) {
            if (!visisted[i]) {     //对未访问的顶点调用DFS()
                DFS(i, visisted);

            }
        }
    }

5.算法复杂度

分析上面的算法,在遍历图时,对图中的每个顶点至多调用一次DFS函数,因为一旦某个顶点被标志为已被访问,就不再从它出发进行深度优先搜索了。因此,遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费时间取决于图所采用的存储结构。

当用二维数组 表示邻接矩阵作图的存储结构时,查找每个顶点的邻接点需要时间为O(n*n),n为顶点的个数。

而当以邻接表作图的存储结构时,查找邻接点的所需时间为O(e),其中e为无向图中边的数,或有向图中弧的个数。

由此,当以邻接表做存储结构时,深度优先搜索遍历图的时间复杂度为O(n+e)

© 著作权归作者所有

啊哈关关
粉丝 9
博文 186
码字总数 80035
作品 0
深圳
程序员
私信 提问
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 一、深度优先搜索 深度优先搜索属于图算法的一种,是一个针对...

安然若知
2018/07/13
0
0
漫画:深度优先遍历 和 广度优先遍历

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/bjweimengshu/article/details/88801664

程序员小灰
03/25
0
0
【译】Swift算法俱乐部-深度优先搜索

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
07/26
0
0
DFS求岛的个数LeetCode 200. Number of Islands

深度优先搜索算法(Depth-First-Search),是搜索算法的一种。它沿着树的深度遍历树的节点,尽可能深的搜索树的分 支。当节点v 的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节...

wall--e
2016/04/15
448
0
算法基础:BFS和DFS的直观解释

算法基础:BFS和DFS的直观解释 https://cuijiahua.com/blog/2018/01/alogrithm_10.html 一、前言 我们首次接触 BFS 和 DFS 时,应该是在数据结构课上讲的 “图的遍历”。还有就是刷题的时候,...

功夫 熊猫
07/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

当阿里云工程师回到了家乡......

根据真实故事改编 略有浮夸 但重要的是 9月25日13:30-16:30 云栖大会「5G边缘计算专场」 一定要来哦 !!! 本文作者:樰篱 原文链接 本文为云栖社区原创内容,未经允许不得转载。...

Mr_zebra
18分钟前
4
0
文件操作工具类 FileUtils常用方法

文件操作工具类(FileUtils) 使用该工具类的前提是项目里导入commons-io 包 import org.apache.commons.io.FileUtils; List<String> lines=new ArrayList<String>(); lines.add("欢迎访问:......

AndLong
24分钟前
3
0
maven-shade-plugin

最近,用规则引擎(drools)的封装了一个jar包,给别人使用。用的是maven-assembly-plugin打的包,可以把多个jar包里的class 给打成一个jar,感觉还是满好用的,但是打包成功后,发现报空指针错...

internetafei
29分钟前
3
0
Cassandra repair 工具使用

前言 Cassandra是一款去中心化的分布式数据库。一份数据会分布在多个对等的节点上,即有多个副本。我们需要定期的对多个副本检查,看是否有不一致的情况。比如因为磁盘损坏,可能会导致副本丢...

阿里云官方博客
32分钟前
4
0
element-vue使用富文本编辑器【前端】

一、前言 1.富文本编辑器选择的为vue-quill-editor 官方地址:https://quilljs.com/docs/quickstart/ 2.安装 cnpm install vue-quill-editor cnpm install quill 3.在对应的页面引入,在com...

一代码农码一代
38分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部