图的深度优先搜索和广度优先搜索

图的深度优先搜索和广度优先搜索具有很多实用价值,我写这两个算法花了好久,最终的到了几个宝贝而惨痛的经验。

总结如下:

1、以图的深度优先搜索未例,该问题本身具有递归的性质,我试着借助栈的来实现深度优先搜索的非递归算法,费了好大的力气,还是没有弄出来。

如果问题本身具有递归性质,则用递归算法几乎是最好的方法。

2、当面临一个复杂问题,该问题中用到了其他的功能,把其中这些功能分出来写成独立的函数实现几乎是最好的方法.从《操作系统的设计和实现》中可以看到,当作者处理一个复杂问题时,并不会考虑其中用的功能如何实现,只用一个函数来表示,这样简化了问题的解答,是解决复杂问题的方法。

3、单步调试威力无穷,当程序在大多数情况下工作正常时,问题出在别的地方。

下面给出图的深度优先搜索算法和广度优先搜索算法:

/*
广度优先遍历算法:(类似层次遍历)
1、首先访问当前顶点v,并设置该顶点的访问标志visited[v]=true。
2、然后访问v的各个未曾被访问过的邻接顶点w1,w2,...wt,然后再访问w1,w2...,wt的
所有未被访问过的邻接顶点。这里需要将先访问的顶点入队,出队。
3、再从这些顶点出发,访问它们未被访问过的邻接点。

具体算法:
1、声明一个visited数组和一个bfs数组用于记录访问与否和访问次序。
2、首先访问结点0。
3、使用STL中的函数库queue来进行队列的入队出队操作。将第一个结点入队。
4、如果该队列不为空,则出队,找到该元素的第一个邻接点。
5、如果该邻接点不为空,且未被访问过,则访问并将该结点入队。
6、找该结点的下一个邻接点。
*/

void LinkedGraph::BFSGraph(LinkedGraph *lg)
{
	cout<<"---------广度优先遍历---------"<<endl;

	bool visited[9];
	int count=0;
	for(int i=0;i<9;i++)	//声明一个访问记录数组
		visited[i]=false;

	int  bfs[9];			//记录访问的次序数组
	//初始化这个数组
	for(int i=0;i<9;i++)
		bfs[i]=0;
	
	//GraphEdge *q;	//用于前一步所访问的顶点,很重要,不可实现
	visited[0]=true;
	bfs[0]=0;
	
	//自己定义的队列有问题,改用C++标准函数库
	//Queue qg;
	//qg.EnQueue(0);	//顶点入队,循环遍历整个图
	queue<int> qg;
	qg.push(0);			//入队
	while(!qg.empty())	//每次访问该层所有的结点
	{
		int d=qg.front();	//将上次访问的顶点出队
		qg.pop();			//出队,并删除第一个元素,猜对了,哈哈
		int w=lg->getFirstNeighbour(d);	//找到顶点d的第一邻接点

		while(w!=-1)	//如果这个邻接点存在
		{
			if(visited[lg->getVerPosition(w)]==false)	//如果顶点没有被访问过
			{
				count++	;	//顶点数加1
				bfs[count]=w;
				int loc=lg->getVerPosition(w);	//获得w的顶点好
				visited[loc]=true;
				qg.push(w);	//将访问过的该结点入队
			}
				w=lg->getNextNeighbour(d,w);	//遍历顶点d的所有邻接点,并且将访问过的结点入队

		}
	}

	//打印顶点的访问次序
	for(int i=0;i<9;i++)
		cout<<bfs[i]<<"--";
	cout<<endl;
}

/*
深度优先搜索算法:(以连通图作为例子)
由于要用到上一次访问过的结点,用一个辅助栈来表示。
1、给定一个起始顶点,每一步探查过程中,首先对当前顶点进行访问,并立即设置该
顶点的访问标志为true。
2、接着在v的所有邻接点中选一个未被访问的作为当前的探查结点,
3、如果当前顶点的所有邻接点都已经被访问过,则把上一次访问的顶点取出,当做探查的当前顶点.

*/

程序的算法以程序的注释为准:

void LinkedGraph::DFSGraph(LinkedGraph *lg,int data)
{
	int i;
	bool visited[9];
	for(i=0;i<9;i++)visited[i]=false;
	DFSGraph(lg,data,visited);			//递归处理
}

void LinkedGraph::DFSGraph(LinkedGraph *lg,int data,bool visited[])
{
	//递归子程序
	cout<<v[lg->getVerPosition(data)].data<<" ";	//打印该结点
	visited[lg->getVerPosition(data)]=true;			//设置该结点的访问标志为true
	int w=lg->getFirstNeighbour(data);	//找第一个邻接点
	while(w!=-1)				//邻接点存在
	{
		if(visited[lg->getVerPosition(w)]==false)	//如果这个顶点没有被访问过
		DFSGraph(lg,w,visited);	//递归的访问当前顶点
		w=lg->getNextNeighbour(data,w);	//找下一个邻接点
	}

}

运行的结果如下:

---------广度优先遍历---------
0--1--2--3--4--5--6--7--8--
----------图的深度优先搜索------
0 1 4 6 2 5 3 7 8
------------------结束---------------

 

原文链接: https://www.cnblogs.com/fistao/archive/2013/05/04/3059644.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

    图的深度优先搜索和广度优先搜索

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/87138

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月9日 下午10:56
下一篇 2023年2月9日 下午10:57

相关推荐