【图的DFS】图的DFS非递归算法
博客专区 > htq 的博客 > 博客详情
【图的DFS】图的DFS非递归算法
htq 发表于1年前
【图的DFS】图的DFS非递归算法
  • 发表于 1年前
  • 阅读 25
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

在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的路径可能不止一种情况,如上述输出表示存在两种情况。


共有 人打赏支持
htq
粉丝 17
博文 67
码字总数 1007
作品 3
×
htq
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: