文档章节

数据结构---->图的遍历

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 1294
阅读 2
收藏 0
点赞 0
评论 0

三 图的遍历

遍历定义:从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做图的遍历,它是图的基本运算。

避免重复访问?

图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了保证图中的各个顶点在遍历过程中访问且仅被访问一次,需要为每个顶点设一个访问标志,Vertex 类中的visited成员变量可以用来作为是否被访问过的标志。

3.1深度优先搜索( DFS )Depth First Search

深度优先搜索(depth firstsearch)遍历类似于树的先根遍历,是树的先根遍历的推广。

深度优先搜索的基本方法是:从图中某个顶点发v 出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

无向图(a)得到的遍历序列为:a , b ,c , e , f , d。

有向图(b)得到的遍历序列为:a , b ,e , c , f , d。

//对图进行深度优先遍历
	public Iterator DFSTraverse(Vertex v) {
		LinkedList traverseSeq = new LinkedListDLNode();//遍历结果
		resetVexStatus();			//重置顶点状态
		DFSRecursion(v, traverseSeq);		//从v点出发深度优先搜索
		Iterator it = getVertex();	//从图中未曾访问的其他顶点出发重新搜索
		for(it.first(); !it.isDone(); it.next()){
			Vertex u = (Vertex)it.currentItem();
			if (!u.isVisited()) DFSRecursion(u, traverseSeq);
		}
		return traverseSeq.elements();
	}

3.1.1 DFSTraverse递归实现

//深度优先的递归算法
	private void DFSRecursion(Vertex v, LinkedList list){
		v.setToVisited();
		list.insertLast(v);
		Iterator it = adjVertexs(v);//取得顶点v的所有邻接点
		for(it.first(); !it.isDone(); it.next()){
			Vertex u = (Vertex)it.currentItem();
			if (!u.isVisited()) DFSRecursion(u,list);
		}
	}


3.1.2使用堆栈以非递归的形式实现

图的深度优先搜索算法也可以使用堆栈以非递归的形式实现,使用堆栈实现深度优先搜索的思想如下:

⑴ 首先将初始顶点v入栈;

⑵ 当堆栈不为空时,重复以下处理

栈顶元素出栈,若未访问,则访问之并设置访问标志,将其未曾访问的邻接点入栈;

⑶ 如果图中还有未曾访问的邻接点,选择一个重复以上过程。

算法DFS的非递归实现

//深度优先的非递归算法
	private void DFS(Vertex v, LinkedList list){
		Stack s = new StackSLinked();
		s.push(v);
		while (!s.isEmpty()){
			Vertex u = (Vertex)s.pop();
			if (!u.isVisited()){
				u.setToVisited();
				list.insertLast(u);
				Iterator it = adjVertexs(u);
				for(it.first(); !it.isDone(); it.next()){
					Vertex adj = (Vertex)it.currentItem();
					if (!adj.isVisited()) s.push(adj);
				}
			}//if
		}//while
	}

3.2广度优先搜索( BFS )Breadth First Search

广度优先搜索(breadth firstsearch) 遍历类似于树的层次遍历,它是树的按层遍历的推广。

假设从图中某顶点v 出发,在访问了v 之后依次访问v 的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”先被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

图(a)中无向图的广度优先搜索遍历序列为:a , b , d , e , c , f;

图(b)中有向图的广度优先搜索遍历序列为:a , b , e , c , f , d。

通过上述搜索过程,我们发现,广度优先搜索遍历图的过程实际上就是以起始点v 为起点,由近至远,依次访问从v 出发可达并且路径长度为1、2、…的顶点。

广度优先搜索遍历的实现与树的按层遍历实现一样都需要使用队列,使用队列实现广度优先搜索的思想如下:

① 首先访问初始顶点v 并入队;

② 当队列不为空时,重复以下处理

队首元素出队,访问其所有未曾访问的邻接点,并它们入队;

③ 如果图中还有未曾访问的邻接点,选择一个重复以上过程。

广度优先遍历BFSTraverse

//对图进行广度优先遍历
	public Iterator BFSTraverse(Vertex v) {
		LinkedList traverseSeq = new LinkedListDLNode();//遍历结果
		resetVexStatus();			//重置顶点状态
		BFS(v, traverseSeq);		//从v点出发广度优先搜索
		Iterator it = getVertex();	//从图中未曾访问的其他顶点出发重新搜索
		for(it.first(); !it.isDone(); it.next()){
			Vertex u = (Vertex)it.currentItem();
			if (!u.isVisited()) BFS(u, traverseSeq);
		}
		return traverseSeq.elements();
	}
	private void BFS(Vertex v, LinkedList list){
		Queue q = new QueueSLinked();
		v.setToVisited();
		list.insertLast(v);
		q.enqueue(v);
		while (!q.isEmpty()){
			Vertex u = (Vertex)q.dequeue();
			Iterator it = adjVertexs(u);
			for(it.first(); !it.isDone(); it.next()){
				Vertex adj = (Vertex)it.currentItem();
				if (!adj.isVisited()){
					adj.setToVisited();
					list.insertLast(adj);
					q.enqueue(adj);
				}//if
			}//for
		}//while
	}

 

© 著作权归作者所有

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
几种数据存储结构详解

影响空间规模的几种数据存储结构 正文 所谓数据存储结构,就是数据的元素与元素之间在计算机中的一种表示,它的目的是为了解决空间规模问题,或者是通过空间规模问题从而间接地解决时间规模问...

长平狐 ⋅ 2012/11/12 ⋅ 1

数据结构之图(存储结构、遍历)

  新学期开始了,开始专心于技术上了,上学期的寒假总是那么短暂,飘飘乎就这样逝去,今天补补上学期还没学完的数据结构---图,希望能和大家一起探讨,共同进步~ 定义:   图是由顶点集合...

graylee ⋅ 2015/03/10 ⋅ 0

数据结构第12讲 二叉树的层次遍历

数据结构第12讲 二叉树的层次遍历 二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示: ...

rainchxy ⋅ 2017/11/14 ⋅ 0

图的JS实现

图的定义 图就是由若干个顶点和边连接起来的一种结构。很多东西都可以用图来说明,例如人际关系,或者地图。 其中图还分为有向图和无向图。 如下就是有向图 图的数据结构 对于图这种关系,可...

光哥很霸气 ⋅ 2017/10/12 ⋅ 0

Redis源码分析(skiplist)

源码版本: 源码位置: server.h :和的数据结构定义。 t_zset.c: 以zsl开头的函数是SkipList相关的操作函数。 一、跳跃表简介 跳跃表(SkipList),其实也是解决查找问题的一种数据结构,但是它...

yangbodong22011 ⋅ 2017/11/13 ⋅ 0

图数据挖掘浅析

互联网发展至今,数据规模越来越大,数据结构越来越复杂,而且对系统的需求越来越高。如果学习过数据结构,那么都知道图是放在最后一个结构,当你学习了图,那么应该感知到前面的链表,队列,...

Bieber ⋅ 2014/08/22 ⋅ 12

数据结构

算法,解决问题之道,各行各业,各门各类均有其固有的难题,而解决问题之道大不相同,社会学,历史学,计算机学,金融学,国学,天文学问题虽不同,但其思维方式却是相通的。 古有筹策论,今...

HappyBoyLi ⋅ 2016/03/04 ⋅ 0

图论 应用篇

上次写了篇图的基本构造方法,运用图这种强大的数据结构结构,还能解决实际应用中的许多问题,今天这篇就主要整理一些常见的应用 一、路径问题 路径问题在图的处理领域是非常重要的。如我们最...

丶legend ⋅ 2017/11/05 ⋅ 0

图结构(Graph)

定义:图可以理解由顶点集合V和边的集合E构成的一种数据结构 G=(V,E)。图的边可用括号括住两个顶点来表示,通常用圆括号 表示无向图的边,尖括号表示有向图的边。 定义:与一个顶点...

RapidBird ⋅ 2010/03/25 ⋅ 0

图形数据库、NOSQL和Neo4j

简介 在众多不同的数据模型里,关系数据模型自80年代就处于统治地位,而且有不少实现,如Oracle、MySQL和MSSQL,它们也被称为关系数据库管理系统(RDBMS)。然而,最近随着关系数据库使用案例...

欧德高 ⋅ 2010/09/09 ⋅ 3

没有更多内容

加载失败,请刷新页面

加载更多

下一页

RabbitMQ学习以及与Spring的集成(三)

本文介绍RabbitMQ与Spring的简单集成以及消息的发送和接收。 在RabbitMQ的Spring配置文件中,首先需要增加命名空间。 xmlns:rabbit="http://www.springframework.org/schema/rabbit" 其次是模...

onedotdot ⋅ 27分钟前 ⋅ 0

JAVA实现仿微信红包分配规则

最近过年发红包拜年成为一种新的潮流,作为程序猿对算法的好奇远远要大于对红包的好奇,这里介绍一种自己想到的一种随机红包分配策略,还请大家多多指教。 算法介绍 一、红包金额限制 对于微...

小致dad ⋅ 39分钟前 ⋅ 0

Python 数电表格格式化 xlutils xlwt xlrd的使用

需要安装 xlutils xlwt xlrd 格式化前 格式化后 代码 先copy读取的表格,然后按照一定的规则修改,将昵称中的学号提取出来替换昵称即可 from xlrd import open_workbookfrom xlutils.copy ...

阿豪boy ⋅ 今天 ⋅ 0

面试题:使用rand5()生成rand7()

前言 读研究生这3 年,思维与本科相比变化挺大的,这几年除了看论文、设计方案,更重要的是学会注重先思考、再实现,感觉更加成熟吧,不再像个小P孩,人年轻时总会心高气傲。有1 道面试题:给...

初雪之音 ⋅ 今天 ⋅ 0

Docker Toolbox Looks like something went wrong

Docker Toolbox 重新安装后提示错误:Looks like something went wrong in step ´Checking if machine default exists´ 控制面板-->程序与应用-->启用或关闭windows功能:找到Hyper-V,如果处......

随你疯 ⋅ 今天 ⋅ 0

Guacamole 远程桌面

本文将Apache的guacamole服务的部署和应用,http://guacamole.apache.org/doc/gug/ 该链接下有全部相关知识的英文文档,如果水平ok,可以去这里仔细查看。 一、简介 Apache Guacamole 是无客...

千里明月 ⋅ 今天 ⋅ 0

nagios 安装

Nagios简介:监控网络并排除网络故障的工具:nagios,Ntop,OpenVAS,OCS,OSSIM等开源监控工具。 可以实现对网络上的服务器进行全面的监控,包括服务(apache、mysql、ntp、ftp、disk、qmail和h...

寰宇01 ⋅ 今天 ⋅ 0

AngularDart注意事项

默认情况下创建Dart项目应出现以下列表: 有时会因为不知明的原因导致列表项缺失: 此时可以通过以下步骤解决: 1.创建项目涉及到的包:stagehand 2.执行pub global activate stagehand或pub...

scooplol ⋅ 今天 ⋅ 0

Java Web如何操作Cookie的添加修改和删除

创建Cookie对象 Cookie cookie = new Cookie("id", "1"); 修改Cookie值 cookie.setValue("2"); 设置Cookie有效期和删除Cookie cookie.setMaxAge(24*60*60); // Cookie有效时间 co......

二营长意大利炮 ⋅ 今天 ⋅ 0

【每天一个JQuery特效】淡入淡出显示或隐藏窗口

我是JQuery新手爱好者,有时间就练练代码,防止手生,争取每天一个JQuery练习,在这个博客记录下学习的笔记。 本特效主要采用fadeIn()和fadeOut()方法显示淡入淡出的显示效果显示或隐藏元...

Rhymo-Wu ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部