文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 1294
阅读 6
收藏 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
	}

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2012/12/27/5637137.html

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

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

长平狐
2012/11/12
753
1
数据结构之图(存储结构、遍历)

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

graylee
2015/03/10
0
0
数据结构第12讲 二叉树的层次遍历

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

rainchxy
2017/11/14
0
0
图的JS实现

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

光哥很霸气
2017/10/12
0
0
用js来实现那些数据结构16(图02-图的遍历)

  上一篇文章我们简单介绍了一下什么是图,以及用JS来实现一个可以添加顶点和边的图。按照惯例,任何数据结构都不可或缺的一个point就是遍历。也就是获取到数据结构中的所有元素。那么图当...

zaking
05/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

新工作与老项目

新的工作不知不觉的干了一个多月了。怎么说呢,跟想象中的差别不少,本来想的能进来跟大公司的同事能有很多交流,能在团队中跟大牛学习更快。结果公司的这个项目上只有两个程序员,项目是十年...

zypy333
10分钟前
0
0
mysql 在windows的安装

mysql 在windows的安装。 mysql64位的server的下载地址是: https://dev.mysql.com/downloads/mysql/ 使用的是5.7版本。 下载安装包,解压至D:\mysql\mysql-5.7.23-winx64\ 在D:\mysql\mysq...

lxzh504
23分钟前
1
0
云技术、大数据(hadoop)入门常见问题回答

当我们学习一门新技术的时候,我们总是产生各种各样的问题,这些问题整理出来,包括该 1.如何学习hadoop? 2.hadoop常见问题? 3.还有hbase、hive安装使用等? 你知道搭建hadoop平台需要些什...

董黎明
23分钟前
1
0
小程序自定义底部tab

场景 1.tabBar是在内页而非首页,这时就不得不自定义一个tabBar了 2.自定义风格 3.子页数量超过5个,得到更多了tab 4.改变点击tab默认事件,比如出登录界面,或者弹出上拉子菜单等 步骤 1.照...

萤火的萤火
28分钟前
1
0
shell炫技

1.为脚本添加“--help” #!/bin/shif [ ${#@} -ne 0 ] && [ "${@#"--help"}" = "" ]; then printf -- '...help...\n'; exit 0;fi; 2.输出字体添加颜色 https://misc.flogisoft.com......

HJCui
29分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部