BFS是什么就不多少了
直接来个题目---倒油：
有一位厨师要从盛12斤油（a桶）的桶中倒出6斤油来，可是手边只有盛8斤油（b桶）和盛5斤油（c桶）的两个桶，问如何操作才能将6斤取出来呢？
题解：
采用面向对象去做，面向对象最主要的是要注意引用直接的捆绑，这个是采用面向对象解题的一大坑，很练手，可以加大对引用和基本数据类型的认识。具体过程如下（有3个类）：
主类：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;/*** Time：2018/3/29* Description：进行解决倒油问题的主类* @author 宋进宇*/
public class PourOil {public static void main(String[] args) {Buckets buckets=init();//初始化化根节点//广搜必备的队列Queue<Buckets> que = new LinkedList<Buckets>();que.add(buckets);//用来记录树所有节点ArrayList<Buckets> list = new ArrayList<Buckets>();list.add(buckets);bfs(que,list);}/*** 广搜 --- 找出最短倒出6斤油的路径* @param que 进行广搜的辅助队列* @param list 存放每个节点的情况*/private static void bfs(Queue<Buckets> que, ArrayList<Buckets> list) {//取出队首Buckets buckets = que.poll();if (buckets==null) {return ;}//只要有一个油桶的油量为6斤就打印路径for (int i = 0; i < buckets.getOilBuckets().length; i++) {if (buckets.getOilBuckets()[i].getExist()==6) {print(buckets);return;}}//备份节点Buckets temp = new Buckets(buckets);//buckets 的子节点//油桶i给油桶j倒油for (int i = 0; i < temp.getOilBuckets().length; i++) {for (int j = 0; j < temp.getOilBuckets().length; j++) {if (i==j) {//自己给自己倒油没意义continue;}//i给j倒油int add = temp.getOilBuckets()[j].add(temp.getOilBuckets()[i]);if (add==0) {//如果倒出空就与 buckets 情况相同，即跳过continue;}//倒出油的情况Buckets newBuckets = new Buckets(temp);//如果先前没有出现过这种情况，则是该树节点加人队列if (!list.contains(newBuckets)) {newBuckets.setParent(buckets);list.add(newBuckets);que.add(newBuckets);}//把油倒回去，继续找 buckets 的子节点temp.getOilBuckets()[j].pourOut(temp.getOilBuckets()[i],add);}}bfs(que, list);}/*** 打印一条路径* @param buckets 该路径的叶子节点 也就是 最底层的节点*/private static void print(Buckets buckets) {if (buckets==null) {return ;}Buckets parent = buckets.getParent();StringBuilder sb = new StringBuilder(buckets.toString());while(parent!=null){sb.insert(0, parent.toString());parent = parent.getParent();}System.out.println(sb.toString());}/*** 初始化油桶的集合* @return 油桶的集合*/private static Buckets init() {Buckets buckets = new Buckets();OilBucket obs[] =new OilBucket[3];obs[0] = new OilBucket(12, 12);obs[1] = new OilBucket(8, 0);obs[2] = new OilBucket(5, 0);buckets.setOilBuckets(obs);return buckets;}
}辅助类（树的节点）：
/*** Time：2018/3/29* Description：存放油桶的数组对象* @author 宋进宇*/public class Buckets {private OilBucket[] oilBuckets;//用对象数组存放所有油桶private Buckets parent; //记录父节点/*** 空参构造*/public Buckets() {}/*** 拷贝对象的构造函数 ---深拷贝（解除引用赋值捆绑）* @param buckets 被拷贝的对象*/public Buckets(Buckets buckets) {if (buckets==null||buckets.oilBuckets.length==0) {return; }this.oilBuckets = new OilBucket[buckets.oilBuckets.length];for (int i = 0; i < buckets.oilBuckets.length; i++) {this.oilBuckets[i] = new OilBucket(buckets.oilBuckets[i].getVolume(), buckets.oilBuckets[i].getExist());}}/*** 获取父节点对象* @return 父节点*/public Buckets getParent() {return parent;}/*** 设置父节点* @param parent 父节点*/public void setParent(Buckets parent) {this.parent = parent;}/*** 获取油桶的集合* @return 油桶的集合*/public OilBucket[] getOilBuckets() {return oilBuckets;}/*** 设置油桶的集合* @param oilBuckets 油桶的集合*/public void setOilBuckets(OilBucket[] oilBuckets) {this.oilBuckets = oilBuckets;}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;Buckets other = (Buckets) obj;///以下是根据题目需求来判断是否相等/for (int i = 0; i < oilBuckets.length; i++) {//只要有一个油桶里面的油量不同 说明两个油桶集合不相同if (oilBuckets[i].getExist()!=other.getOilBuckets()[i].getExist()) {return false;}}return true;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();if (oilBuckets==null||oilBuckets.length==0) {return null;}sb.append(oilBuckets[0].getExist());for (int i = 1; i < oilBuckets.length; i++) {sb.append(","+oilBuckets[i].getExist());}sb.append("\r\n");return sb.toString();}}辅助类（油桶）：
/*** Time:2018/3/29 * Description：油桶---倒油问题所需对象* @author 宋进宇**/
public class OilBucket {private int volume;// 油桶的容量private int exist;// 油桶里已有的油public OilBucket() {}/*** 构造一个油桶* @param volume 油桶的容量* @param exist 油桶里已有的油*/public OilBucket(int volume, int exist) {super();this.volume = volume;this.exist = exist;}/*** 把油桶ob中油倒入当前对象中* * @param ob 倒出油的对象* * @return 表示倒入油的数量*/public int add(OilBucket ob) {if (ob == null) {return 0;}int add = 0;if (volume>=exist+ob.exist) {add=ob.exist;exist += ob.exist;ob.exist =0;}else{add = volume-exist;ob.exist -= add;exist = volume;}return add;}/*** 把当前对象中的油倒入ob中* * @param ob 被倒入油的对象* * @return 表示倒出油的数量*/public void pourOut(OilBucket ob,int value) {if (ob==null) {return ;}exist -= value;ob.exist += value;}public int getVolume() {return volume;}public void setVolume(int volume) {this.volume = volume;}public int getExist() {return exist;}public void setExist(int exist) {this.exist = exist;}}