想进大厂先把广度优先搜索搞懂啰

广度优先搜索的思想就是从起始点开始，一层一层地扫描，找到了目标点则表示搜索成功；

由于广度优先查找是每次遍历完前面的所有节点，所以最先找到节点时对应的路径肯定是最短的

实现思路：

1 使用队列来装节点，将起始节点放入队列，

2 遍历队列，弹出队列元素，标记元素为已访问，判断是否为目标元素，是则成功，返回；否则，将该元素的连接点（nexts）依次加入队尾

重复2的过程，直到找到目标节点时结束循环

下面例子，要求找出点0到点8的最近路线

import java.util.LinkedList;
/**
 * 广度优先遍历，找到最短路径，即返回
 * @author ssj
 *
 */
public class BFSPath {
    public static void main(String[] args) {
        //构造节点
      Node[] nodes = new Node[9];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new Node(i);
        }
        nodes[0].addNexts(nodes[1], nodes[3]);
        nodes[1].addNexts(nodes[0], nodes[2]);
        nodes[2].addNexts(nodes[1], nodes[4], nodes[5]);
        nodes[3].addNexts(nodes[0], nodes[5], nodes[6]);
        nodes[4].addNexts(nodes[2], nodes[8]);
        nodes[5].addNexts(nodes[2], nodes[3], nodes[6], nodes[8]);
        nodes[6].addNexts(nodes[3], nodes[5], nodes[7]);
        nodes[7].addNexts(nodes[6], nodes[8]);
        nodes[8].addNexts(nodes[4], nodes[5], nodes[7]);
      
        Node start = nodes[0];//起始点
        Node end = nodes[8];//搜索的目标点
        boolean hasPath = bfs(start, end);
        if (hasPath) {
            // print path
            Node pre = end;
            do {
                System.out.print(pre.getId() + " -> ");
                pre = pre.getPre();
            } while (pre != null);
        } else {
            System.out.println("找不到要搜索的终点");
        }
    }
    public static boolean bfs(Node start, Node end) {
        LinkedList<Node> queue = new LinkedList<>();
        queue.addLast(start); // 添加到队尾
        while (!queue.isEmpty()) {
            Node vertex = queue.pollFirst(); // 从队首取出一个元素
            // 如果这个顶点是否已经检索过了，则跳过
            if (vertex.isVisted()) {
                continue;
            }
            if (vertex == end) {
                // 如果到了终点了就可以返回了
                return true;
            } else {
                // 如果还不是终点，这把该顶点可以到达的邻居全部添加到队列末端
                for (Node neighbor : vertex.getNexts()) {
                    if (neighbor.getPre() == null && neighbor != start) {
                        neighbor.setPre(vertex);
                    }
                    queue.addLast(neighbor);
                }
            }
            vertex.setVisted(true);
        }
        return false;
    }
    
    
}
class Node {
    private int id; // 顶点的标识
    private LinkedList<Node> nexts; // 这个顶点的邻居顶点
    private boolean isVisted; // 这个顶点是否被搜索过了
    private Node pre; // 这个顶点的前驱，用来记录路径的
    
    public Node(int id) {
        this.id = id;
    }
    
    public void addNexts(Node... vertexes) {
        this.nexts = new LinkedList<>();
        for (Node vertex : vertexes) {
            this.nexts.add(vertex);
        }
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public LinkedList<Node> getNexts() {
		return nexts;
	}
	public void setNexts(LinkedList<Node> nexts) {
		this.nexts = nexts;
	}
	public boolean isVisted() {
		return isVisted;
	}
	public void setVisted(boolean isVisted) {
		this.isVisted = isVisted;
	}
	public Node getPre() {
        return pre;
    }
    public void setPre(Node pre) {
        this.pre = pre;
    }
    
}

输出结果