# ACM入门（3）——图的遍历——广度优先搜索

ACM入门（3）——图的遍历——广度优先搜索

BFS算法：
BFS(G,s)//从s点开始对图G广度优先搜索for each vertex u∈V[G]-{s}        do color← white//每个点赋值为未处理          d←∞  //每个点与源点的距离标志为∞∏←NIL       //每个点赋值为没有父亲color[s] ←gray              //s点标为正在处理d[s] ←0                     //s点与源点的距离为0Q ←ф                   //建空队列保存灰色顶点ENQUEUE(Q,s)       //源点入队列While（Q≠ф）    do u ←DEQUEUE(Q);//从队列中拿出一个元素进行处理         for each v ∈Adj //对没有处理过的邻接点进行处理              do  if  color[v]=white                        then color[v] ←gray                                d[v]=d+1∏[v]=u                                ENQUEUE(Q,v)         color=black//标记为处理完毕

Bfs算法中路径的打印
Print-Path(G,s,v)
①   if(v==s)
②        then print s
③        else if ∏[v]=NIL
④                  then print “no path from ”s”to” v”exits”
⑤                  else Print-path(G,s, ∏[v])
⑥                         print v

HDU1372

Knight Moves
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 859    Accepted Submission(s): 535
Problem Description A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the “difficult” part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.
Input
The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
Output
For each test case, print one line saying “To get from xx to yy takes n knight moves.”.
Sample Input
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

#include <iostream>
#include <queue>
using namespace std;
struct Point//建一个坐标结构体来保存位置坐标
{
int x,y;
Point(int a,int b)//设置构造函数
{
x=a;
y=b;
}
};
bool mark[9][9];//用bool的二维数组来记录某点是否访问过
int map[9][9];//建二维数组来保存图，其数值代表从起始点到此的步数
int step[8][2]={{2,1},{1,2},{-1,2},{2,-1},
{-2,1},{1,-2},{-1,-2},{-2,-1}};//一个8*2的数组代表每次可能走的方式
inline bool in_map(const Point& p)//判断该坐标是否在棋盘内
{
return p.x>0&&p.x<9&&p.y>0&&p.y<9;
}
int main()
{
int a1,a2;
char c1,c2;
while(cin>>c1>>a1>>c2>>a2)
{
memset(mark,false,sizeof(mark));//对标记数组初始化为未标记
memset(map,0,sizeof(map));//对map数组初始化为0步
Point p1(c1-‘a’+1,a1);//用Point保存起点和终点坐标
Point p2(c2-‘a’+1,a2);
queue<Point> q;//建队列保存将要处理的坐标
mark[p1.x][p1.y]=true;//将起点坐标标记为访问过
q.push(p1);//将起点坐标放入队列
while(!q.empty())
{
Point p=q.front();//将队首元素取出
q.pop();//将队首元素删除
if(p.x==p2.x&&p.y==p2.y)//如果当前坐标为终点就跳出循环
break;
for(int i=0;i<8;++i)//循环八次尝试每次所能走的八种情况
{
Point temp(p.x+step[0],p.y+step[1]);//将下一步坐标保存在temp中
if(in_map(temp)&&!mark[temp.x][temp.y])//判断未访问过且在棋盘内
{
mark[temp.x][temp.y]=true;//将其标为访问过
map[temp.x][temp.y]=map[p.x][p.y]+1;//步数在前一步基础上加一
q.push(temp);//同时将其放入队列等待下次操作
}
}
}
cout<<“To get from “<<c1<<a1//按要求输出结果
<<” to “<<c2<<a2
<<” takes “<<map[p2.x][p2.y]
<<” knight moves./n”;
}
return 0;
}

原文作者：数据结构之图
原文地址: https://blog.csdn.net/clbxp/article/details/6575688
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。