关于搜索的问题。

    与树的遍历相同，图遍历操作的定义式访问图中每一个结点且每个结点只被访问一次。图的遍历方法主要有两种：一种是深度优先的（DFS），另一种是广度优先的（BFS）。

   图的遍历算法设计要考虑到三个问题：（1）图的特点是没有首尾之分，所以算法的参数要指定访问的第一个结点；（2）对图的遍历路径有可能是一个回路，从而造成死循环，所以算法设计要考虑到遍历路径可能出现的死循环问题；（3）一个结点可能与若干个结点都是邻接连点，要使一个结点的所有邻接结点按照某种次序被访问。

   DFS（图的深度优先算法）是遍历时深度优先的算法，即在图的所有邻接结点中每次都在访问完成当前结点后首先访问当前结点的第一个邻接结点，这是一个递归算法。

  连通图的深度优先算法为：

a、访问结点v并标记结点v为访问；

b、查找结点v的第一个邻接结点w;

c、若结点v的邻接结点w存在，则继续执行，否则算法结束；

d、若结点w尚未被访问，则递归访问结点w;

e、查找结点v的w邻接结点的下一个邻接结点w,转到步骤c;

  BFS(图的广度优先遍历算法)是一个分层搜索的过程，图的广度搜索算法需要一个队列以保持访问过的结点顺序，以便按顺序访问这些结点的邻接结点。连通图的广度优先算法为：

（1）访问初始结点v并标记结点v为已访问；

（2）结点v入队列；

（3）当队列非空时则继续进行，否则算法结束；

（4）出队列取的头结点u;

（5）查找结点u的第一个邻接结点w;

（6）若结点u的邻接结点w不存在，则转到步骤（3），否则循环执行以下步骤；

   （6.1）若结点w尚未被访问，则访问w并标记w为已访问；

   （6.2）结点w入队列；

   （6.3）查找结点u的w邻接结点的下一个邻接结点，转到步骤（6）；

 

 

poj  3278就是一个典型的广度优先搜索问题：

题意如下：就是给出a和b点的横坐标，求到a，b的最小行动次数，其中每次行动只能是下面两种情况之一

  （1）向左或向右移动一步，即横坐标加1或者减1 ;

  （2）横坐标变成原来的两倍;

  题目给出的数据5 17 ， 可以这样进行行动 5 -> 10 -> 9 -> 18 -> 17 所以只需要四步就可以到达b。

 

 

  因为是求最小行动次数，故可以用BFS，调用STL里面的队列来实现。每次去队首元素，如果到达了b点，输出步子并结束搜索，否则，行动步子+1，并分别将改点的横坐标+1，-1，×2操作后压入队列，一直到寻找到解。注意到当位置的横坐标超过了b点就应该再向右走，故此时应该对其横坐标只有-1操作，还要注意到横坐标为0的特殊情况，此处应该只进行+1行走。刚开始的时候把标记数组开小了，没注意到×2可能会出现超过100,000的情况，提交时RE了一次，把数组改打就AC了。

代码如下：

#include <iostream>
#include <queue>
using namespace std;
const int  Max=100005;

int main()
{
	queue<int> a;
	int n,k;
	cin>>n>>k;
	bool visit[Max];//标记是否访问过
	memset(visit,false,sizeof(visit));
	bool fine=false;
	int step=0;//结果次数
	visit[n]=true;
	a.push(n);
	if (n!=k)
	{
		while (!a.empty()&&!fine)
		{
			int t=a.size();
			step++;
			while (t--)
			{
				int pos,npos[3];
				pos=a.front();
				a.pop();
				npos[0]=pos+1;
				npos[1]=pos-1;
				npos[2]=pos*2;//三种情况
				for (int i=0;i<3;i++)
				{
					if (npos[i]==k)
					{
						fine=true;
						break;
					}
					if (npos[i]>=0&&npos[i]<=10000&&!visit[npos[i]])
					{
						visit[npos[i]]=true;
						a.push(npos[i]);//将位置入队列
					}
				}

			}
		}
	}
	cout<<step<<endl;
	return 0;
}

 

 

 关于搜索的题目还会继续……