文档章节

【图的DFS】图的DFS非递归算法

htq
 htq
发布于 2016/07/26 09:40
字数 589
阅读 33
收藏 0
点赞 0
评论 0

在DFS的递归算法中,DFS框架如下:

1访问起点v0

2依次以v0的未访问的连接点为起点,DFS搜索图,直至图中所有与v0路径相通的顶点都被访问。

3若该图为非连通图,则图中一定还存在未被访问的顶点,选取该顶点为起点,重复上述DFS过程,直至图中全部顶点均被访问过为止。

而在非递归的DFS框架中,运用栈来取代递归(递归的本质就是入栈出栈),所以用自定义的栈取代递归栈,具体框架如下:

1首先初始化待使用栈,然后将第一个结点入栈
2然后只要栈不空,重复下面的操作:将栈顶元素弹出,然后看该元素是否访问过
3若没访问过,则访问,置访问标记,然后将该元素的所有相邻顶点入栈(注意是全部,所以应用一个for或while循环来判断哪些元素该入栈)
4重复2,直至全部顶点均被访问过。

基于上述思路代码如下:

#include<iostream>
using namespace std;
typedef struct node
{
	int t;
	struct node *pnext;
}node,*pnode;
void init(pnode s)
{
	s->pnext=NULL;
}
void push(pnode s,int x)
{
	pnode ptemp=(pnode)malloc(sizeof(node));
	ptemp->t=x;
	ptemp->pnext=s->pnext;
	s->pnext=ptemp;
}
void pop(pnode s,int *x)
{
	pnode ptemp=s->pnext;
	*x=ptemp->t;
	s->pnext=ptemp->pnext;
	free(ptemp);

}
bool isEmpty(pnode s)
{
	pnode p=s->pnext;
	if(NULL==p)
		return true;
	else
		return false;
}
node s;
const int  M=4;
int visit[M];
int arc[M][M]={{0,1,0,0},{1,0,1,0},{0,1,0,1},{0,0,1,0}};

void dfs(int g[][M],int v)
{
	init(&s);//使用自定义栈之前对栈进行初始化
	push(&s,v);
	while(!isEmpty(&s))
	{
		pop(&s,&v);
		if(!visit[v])
		{
			cout<<v<<' ';
			visit[v]=true;
			for(int k=0;k<M;k++)
			{
				if(!visit[k]&&g[v][k]==1)
				{
					push(&s,k);
				}
			}
		}
	}

}
void DFS(int g[M][M],int v)
{
	printf("%d ",v);
	visit[v]=true;
	for(int k=0;k<M;k++)
	{
		if(!visit[k]&&(g[v][k])==1)
			DFS(g,k);
	}
}
void main()
{
	dfs(arc,2);
	for(int i=0;i<M;i++)
	{
		visit[i]=0;
	}
	cout<<'\n';
	DFS(arc,2);
	cout<<'\n';
	for(int i=0;i<M;i++)
	{
		visit[i]=0;
	}
	dfs(arc,2);//求以顶点2为起点的DFS路径
}
程序运行结果如下:



上述输出结果为以顶点2为起点的DFS路径,注意DFS的路径可能不止一种情况,如上述输出表示存在两种情况。


本文转载自:http://blog.csdn.net/htq__/article/details/50856410

共有 人打赏支持
htq

htq

粉丝 19
博文 67
码字总数 1007
作品 3
武汉
【算法研究】搜索算法-深度优先搜索

---------- 如果您觉得本文有用,可以在微博上关注我,每周我都会在微博上发布新博客发表的通知,我的微博 深度优先搜索 介绍 如果您觉得这篇文章排版不舒服,请到我的微盘下载pdf:搜索算法...

王选易 ⋅ 2013/12/13 ⋅ 3

深度优先搜索的实现

图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历。图...

songlee ⋅ 2014/07/05 ⋅ 0

图的广度优先和深度优先遍历(BFS和DFS)

图是一种灵活的数据结构,一般作为一种模型用来定义对象之间的关系或联系。对象由顶点()表示,而对象之间的关系或者关联则通过图的边()来表示。 图可以分为有向图和无向图,一般用来表示...

Shuqing,Wang ⋅ 2017/12/14 ⋅ 0

数据结构学习(一)

数据结构与算法 1. 链表与数组。 2. 队列和栈,出栈与入栈。 3. 链表的删除、插入、反向。 4. 字符串操作。 5. Hash表的hash函数,冲突解决方法有哪些。 6. 各种排序:冒泡、选择、插入、希尔...

技术小甜 ⋅ 2017/11/16 ⋅ 0

数据结构与算法--图论之寻找连通分量、强连通分量

数据结构与算法--图论之寻找连通分量、强连通分量 寻找无向图的连通分量 使用深度优先搜索可以很简单地找出一幅图的所有连通分量,回忆连通图的概念:如果从任意顶点都存在一条路径达到任意一...

sunhaiyu ⋅ 2017/11/11 ⋅ 0

【总结】DFS算法模板及题型分类

DFS算法模板及题型分类 题型分类: 写过这些入门题后,我们可以将DFS题分为两大类: 1 . 地图型:这种题型将地图输入,要求完成一定的任务。因为地图的存在。使得题意清楚形象化,容易理清搜...

chen_yuazzy ⋅ 2017/07/31 ⋅ 0

HDU 1269 迷宫城堡(强连通图的判定)

最近《算法导论》快看完图论部分了,很多有关图的算法都彻底搞懂并加以证明了。现在主要是将理解的思想用到题目中来加强下。这个题目主要是判断一下整个图是否是强连通的,很简单,可以用tar...

iaccepted ⋅ 2015/01/06 ⋅ 0

​数据结构-图之强连通

数据结构-图之强连通 在一个无向图G中,若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径),则称vi和vj是连通的。如果G是有向图,那么连接vi和vj的路径中所有的边都必须同向。如果图...

壶漏子 ⋅ 2015/06/26 ⋅ 0

HDU 2586 How far away ?

How far away ?Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6309 Accepted Submission(s): 2368 include include include u......

iaccepted ⋅ 2015/01/24 ⋅ 0

无向图----深度优先搜索

上一篇:无向图的实现 下一篇:深度优先遍历 根据描述,很容易实现图的深度优先搜索: 深度优先遍历标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比。 使用深度优先搜索查找图中路...

Superheros ⋅ 2017/12/19 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

中标麒麟(龙芯版)7.0优盘安装

########################################## 制作U盘安装盘: 1.准备U盘: PMON环境下U盘必须格式化成ext3; 昆仑固件环境下可以格式化成ext3,ext4 2.把整个镜像 xxx.iso 复制到U盘下面 3....

gugudu ⋅ 17分钟前 ⋅ 0

老司机写的大数据建模五步走

本文将尝试来梳理一下数据建模的步骤,以及每一步需要做的工作。 01 第一步:选择模型或自定义模式 这是建模的第一步,我们需要基于业务问题,来决定可以选择哪些可用的模型。 比如,如果要预...

gulf ⋅ 26分钟前 ⋅ 0

PacificA 一致性协议解读

PacificA 的 paper 在 08 年左右发出来的,比 Raft 早了 6,7 年。 在 PacificA 论文中,他们强调该算法使用范围是 LAN (Local Area Network),讲白了就是对跨机房不友好。 不管是 ZAB,Raf...

黑客画家 ⋅ 29分钟前 ⋅ 0

盘符图标个性化

设置自己的专属盘符图标 准备ico格式的图片文件一个,在根目录下创建autorun.inf文件 文件内容 [Autorun]icon=logo.ico 重新启动或者插拔U盘即可看到结果...

阿豪boy ⋅ 29分钟前 ⋅ 0

Windows下QQ聊天记录中图片的默认存放位置

Windows下QQ聊天记录中图片的默认存放位置在设置中是没有说明的。 实测位置在:D:\Documents\Tencent Files\974101467\Image 其中: “974101467”为对应的QQ号; “C2C”为个人之间的聊天图...

临江仙卜算子 ⋅ 35分钟前 ⋅ 0

GC 的三种基本实现方式

参考资料《代码的未来》(作者: [日] 松本行弘)。 由于并非本人原著(我只是个“搬运工“),SO 未经本人允许请尽情转载。 另外个人像说明一下这里所说的GC指泛指垃圾回收机制,而单指Jav...

xixingzhe ⋅ 36分钟前 ⋅ 0

Android双击退出

/** * 菜单、返回键响应 */ @Override public boolean onKeyDown(int keyCode, KeyEvent event) { // TODO Auto-generated method stub if(keyCode......

王先森oO ⋅ 40分钟前 ⋅ 0

idea 整合 vue 启动

刚学习Vue 搭建了一个项目 只能命令启动 Idea里面不会启动 尝试了一下修改启动的配置 如下: 1.首先你要保证你的package.json没有修改过 具体原因没有看 因为我改了这个name的值 就没办法启动...

事儿爹 ⋅ 46分钟前 ⋅ 0

redis在windows环境的后台运行方法

在后台运行,首先需要安装redis服务,命令为 redis-server.exe --service-install redis.windows.conf --loglevel verbose 启动,命令为 redis-server --service-start 停止,命令为 redis-...

程序羊 ⋅ 49分钟前 ⋅ 0

比特币现金开发者提出新的交易订单规则

本周,四位比特币现金的四位开发者和研究员:Joannes Vermorel(Lokad),AmaurySéchet(比特币ABC),Shammah Chancellor(比特币ABC)和Tomas van der Wansem(Bitcrust)共同发表了一篇关...

lpy411 ⋅ 53分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部