在搜素算法当中，广度优先搜索BFS（Breadth First Search）大概是最简单、暴力的一种搜索算法。BFS的广度优先的广度，实际上是“同权重同步考虑”的广度，用队列queue作为实现核心。BFS的核心思路是：
（1）起点入队。
（2）队列循环，循环条件是队列非空!q.empty();
（3）队头出队
（4）如果出队的值是想要的值，结束搜索，不然对出队的值进行位移：
对于每一个点（数值），存在有限个改变点值的方向（值位移函数），这通常用一个循环结构来实现，改变点值的方向数称为值位移周期，也是循环结构的循环数。在这个周期内产生的数的权重是一样的，而后面周期产生的数的权重都比前一个的低。“权重”的思想并不用在程序中体现，只是在这里解释BFS的实现核心思想，就是“分身走迷宫”。
（5）每产生一个新的数，只要它没有被访问过（队列中以前保存过了），就入队。
（6）直到队列跑空都没有找到，说明没有解。
本文将以POJ3414题为例，作为典型记录一下单纯的BFS题可能遇到的情况（多接口和记录路径），下面先放题目：
你有有两个罐子，分别是A升和B升的体积。可以执行以下操作:
FILL(i)从水龙头中填充罐i(1≤i≤2);
DROP(i)罐i排空到排水管;
POUR(i,j)从罐i倒到罐j;在这个操作之后，要么罐子j是满的(而且罐子i可能还有一些水)，要么罐子i是空的(它的所有内容都被移动到罐子j)。
编写一个程序，找出这些操作的最短可能序列，使其中一个罐子恰好产生C升的水。
Input:
第一行也是唯一一行是数字A、B、C。这些都是1 ~ 100之间的整数，且C≤max(A、B)。
Output:
输出的第一行必须包含操作序列K的长度，接下来的K行必须描述一个操作。如果有几
个最小长度的序列，输出其中任何一个。如果无法达到预期的结果，文件的第一行也
是唯一一行必须包含单词“impossible”。
Sample Input
3 5 4
Sample Output
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
先分析题目，本题是很经典的BFS题，主要有以下特征：明确的起点状态（A,B都空）和终点状态（其中一个中的水量＝C），有限个值位移方向（FILL,DROP和POUR），以及明确的边界条件（两个桶的容积），同时要求找到最优解（步骤最短）。
本题需要储存状态（两个水桶当前的水量），这个状态本身就是多接口的（有两个桶），随后需要记录步骤，本文重在解释BFS记录步骤的思路（类单链表）。先解释一下本题需要的接口。
首先，在BFS中，每一个父结点会根据值位移函数提供的方向派生出多个子结点，例如在本题中，值位移函数事实上提供了6个状态改变方向（Fill(i),Fill(j),Drop(i),Drop(j),Pour(i,j),Pour(j,i)）因此每一个父结点（前一状态）会派生出6个子节点（后一状态），简化这个问题，即1会派生出234567，而A会派生出BCDEFG，我们只需要给它们每一个结点一个独一无二的标识符（下标），同时在子结点中储存父结点的下标，这样我们就可以根据最终状态一路追踪到最早的父结点，这里的思想有点类似于“并查集”，但笔者做此题时还未接触并查集的概念，因此用单链表作比喻。下面给出值位移函数和接口：
状态和操作链（BFS单位元）：
class pot{ //BFS*-对于多入口的复杂BFS，需要类/结构体来储存入口
public:
int x , y; //当前两个瓶子的剩余水量(状态)
int pos; //记录当前状态在操作链p中的下标
int step; //当前步数
};
class process{ //操作链
public:
int pre; //记录上一个操纵的下标
string op; //记录操作
};值位移函数：
void Fill(int i){
switch(i){
case 1: k1 = v1; return;
case 2: k2 = v2; return;
}
}
void Drop(int i){
switch(i){
case 1: k1 = 0; return;
case 2: k2 = 0; return;
}
}
void Pour(int i, int j){
switch(i){
case 1:if(k1+k2<=v2){
k2 += k1;
k1 = 0;
}
else{
k1 = k1+k2-v2;
k2 = v2;
}return;
case 2:if(k2+k1<=v1){
k1 += k2;
k2 = 0;
}
else{
k2 = k1+k2-v1;
k1 = v1;
}return;
}
}
string dev(int k, int i, int j){
switch(k){
case 0: Fill(i); return "Fill(1)";
case 1: Fill(j); return "Fill(2)";
case 2: Drop(i); return "Drop(1)";
case 3: Drop(j); return "Drop(2)";
case 4: Pour(i,j); return "Pour(1,2)";
case 5: Pour(j,i); return "Pour(2,1)";
}
}对于BFS，一个很重要的模块是“标记访问”，标记访问过的状态，避免被后来的访问覆盖状态，由于不同题目的状态是五花八门的，但字符串基本可以解决大部分问题，所以常用map<string,bool>来标记访问，在本题中，将剩余水量a，b组成字符串来标记访问，首先给出组合函数：
string combAB(int a,int b) //把整数a、b整合为 "a,b" 的字符串形式(不包括引号)，用于标记状态
{
string s;
{ ostringstream oss;
oss<<a;
oss<<',';
oss<<b;
s=oss.str();
}
return s;
}由于完成BFS后，对步骤的追述是倒序的，而最后输出需要正序输出，用栈stack可以简单地解决这个问题。
最后放出源码：
#include<bits/stdc++.h>
using namespace std;
int v1 , v2; //瓶子容量
int c; //目标水量
int k1 , k2; //瓶子内含水量
class pot{ //BFS*-对于多入口的复杂BFS，需要类/结构体来储存入口
public:
int x , y; //当前两个瓶子的剩余水量(状态)
int pos; //记录当前状态在操作链p中的下标
int step; //当前步数
};
class process{ //记录操作链
public:
int pre; //记录上一个操纵的下标
string op; //记录操作
};
string combAB(int a,int b) //把整数a、b整合为 "a,b" 的字符串形式(不包括引号)，用于标记状态
{
string s;
{ ostringstream oss;
oss<<a;
oss<<',';
oss<<b;
s=oss.str();
}
return s;
}
//BFS-值位移函数
void Fill(int i){
switch(i){
case 1: k1 = v1; return;
case 2: k2 = v2; return;
}
}
void Drop(int i){
switch(i){
case 1: k1 = 0; return;
case 2: k2 = 0; return;
}
}
void Pour(int i, int j){
switch(i){
case 1:if(k1+k2<=v2){
k2 += k1;
k1 = 0;
}
else{
k1 = k1+k2-v2;
k2 = v2;
}return;
case 2:if(k2+k1<=v1){
k1 += k2;
k2 = 0;
}
else{
k2 = k1+k2-v1;
k1 = v1;
}return;
}
}
string dev(int k, int i, int j){
switch(k){
case 0: Fill(i); return "Fill(1)";
case 1: Fill(j); return "Fill(2)";
case 2: Drop(i); return "Drop(1)";
case 3: Drop(j); return "Drop(2)";
case 4: Pour(i,j); return "Pour(1,2)";
case 5: Pour(j,i); return "Pour(2,1)";
}
}
void BFS(){
queue<pot> q; //BFS-核心队列
put head , next;
process p[1000];
map<string,bool> vis; //BFS-访问标记
head.x = 0;
head.y = 0;
head.pos = 0;
q.push(head);
int ptr = 0; //记录操作下标：
while(!q.empty()){
head = q.front();
q.pop();
for(int k=0;k<6;k++){
k1 = head.x;
k2 = head.y;
string st = dev(k,1,2); //临时储存操作
string str = combAB(k1,k2);
if(vis[str]) continue;
next.pos = ptr++;
p[next.pos].pre = head.pos;
p[next.pos].op = st; //未被跳过，入列
next.x = k1;
next.y = k2;
next.step = head.step + 1;
vis[str] = true;
q.push(next);
if(next.x==c || next.y==c){
cout<<next.step<<endl; //输出步数
stack<string> s; //用栈完成倒序输出
int k = next.pos;
for(int i=0;i<next.step;i++){
s.push(p[k].op);
k = p[k].pre;
}
while(!s.empty()){
cout<<s.top()<<endl;
s.pop();
}
return;
}
}
}
cout<<"impossible"<<endl;
}
int main(){
cin>>v1>>v2>>c;
BFS();
} 本篇博客写得比较草率，因为BFS是相对入门的搜索技术，只需要掌握以下要点：
1、构建合适的核心队列queue，队列的类型应该和单位元一致。
2、BFS需要访问标记，避免丢失最优解。
3、确立值位移函数，它决定了子节点的个数。
4，确立边界，越界的子节点是不被允许的。