文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 1294
阅读 24
收藏 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
广州
私信 提问
加载中
请先登录后再评论。
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2
C++模板库--C++ B-tree

这是一个google开源的C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btreemap、btreeset、btreemultimap和btreemu...

匿名
2013/02/05
3.4K
1
开源数据访问组件--Smark.Data

Smark.Data是基于Ado.net实现的数据访问组件,提供基于强类型的查询表达式进行灵活的数据查询,统计,修改和删除等操作;采用基于条件驱动的操作模式,使数据操作更简单轻松;内部通过标准SQL...

泥水佬
2013/03/12
2.6K
0
服务器自动化任务解决方案--Huginn

Huginn 是雅虎开发的一个系统,可以帮你执行自动化的在线任务。可以阅读网页,关注事件,并采取相应操作。Huginn 通过一个直观的事件流图来展示各种操作和事件。通过在你自己的服务器上的管道加...

匿名
2013/03/15
1.7W
0
数据中心生命周期管理--Foreman

Foreman是一个集成的数据中心生命周期管理工具,提供了服务开通,配置管理以及报告 功能,和Puppet Dahboard一样,Foreman也是一个Ruby on Rails程序.Foreman和 Dashboard不同的地方是在于,Fore...

匿名
2012/10/24
1.5W
0

没有更多内容

加载失败,请刷新页面

加载更多

Hacker News 简讯 2020-08-15

最后更新时间: 2020-08-15 04:01 Welders set off Beirut blast while securing explosives - (maritime-executive.com) 焊工在固定炸药的同时引爆了贝鲁特爆炸 得分:215 | 评论:209 Factor......

FalconChen
今天
24
0
OSChina 周六乱弹 —— 老椅小猫秋乡梦 梦里石台堆小鱼

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @小小编辑 :《MOM》- 蜡笔小心 《MOM》- 蜡笔小心 手机党少年们想听歌,请使劲儿戳(这里) @狄工 :腾讯又在裁员了,35岁以上清退,抖音看到...

小小编辑
今天
71
1
构建高性能队列,你不得不知道的底层知识!

前言 本文收录于专辑:http://dwz.win/HjK,点击解锁更多数据结构与算法的知识。 你好,我是彤哥。 上一节,我们一起学习了如何将递归改写为非递归,其中,用到的数据结构主要是栈。 栈和队列...

彤哥读源码
今天
17
0
Anaconda下安装keras和tensorflow

Anaconda下安装keras和tensorflow 一、下载并安装Anaconda: Anaconda下载 安装步骤: 如果是多用户操作系统选择All Users,单用户选择Just Me 选择合适的安装路径 然后勾选这个,自动配置环境...

Atlantis-Brook
今天
15
0
滴滴ElasticSearch千万级TPS写入性能翻倍技术剖析

桔妹导读:滴滴ElasticSearch平台承接了公司内部所有使用ElasticSearch的业务,包括核心搜索、RDS从库、日志检索、安全数据分析、指标数据分析等等。平台规模达到了3000+节点,5PB 的数据存储...

滴滴技术
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部