Java实现广度优先算法-找出图中两个节点的最短路径。

广度优先算法，用来查找图中两个节点的最短路径。这里的最短是指最短边数。

思路：从起点开始，依次把自己的邻居放入待搜索队列。然后每次从队列弹出头部，判断是不是要找的节点，不是就把自己的邻居放入队列。这样搜索的顺序就是一层一层的，找到的时候路径也是最短的。

下面是代码。采用邻接表来实现图。adjList是这个图的邻接表。waitSearchQueue是等待搜索的队列。visitedList是已经搜索过的节点散列表。

public class GraphBfs {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();//key是id value是他的邻居

    //初始化图
    public void initialGraph(){
        List<Integer> adj1 = new LinkedList<>();
        adj1.add(2);
        adj1.add(3);
        List<Integer> adj2 = new LinkedList<>();
        adj2.add(4);
        adj2.add(5);
        List<Integer> adj3 = new LinkedList<>();
        adj3.add(4);
        adj3.add(6);
        List<Integer> adj4 = new LinkedList<>();
        adj4.add(5);
        List<Integer> adj5 = new LinkedList<>();
        adj5.add(6);
        List<Integer> adj6 = new LinkedList<>();
        this.adjList.put(1,adj1);
        this.adjList.put(2,adj2);
        this.adjList.put(3,adj3);
        this.adjList.put(4,adj4);
        this.adjList.put(5,adj5);
        this.adjList.put(6,adj6);
    }

    //广度优先 寻找最短路径
    public void bfs(int startId,int endId){
        Queue<Node> waitSearchQueue = new LinkedList<>();//等待被搜索的队列
        Map<Integer,Node> visitedList = new HashMap<>(); //访问过的节点列表
        waitSearchQueue.offer(new Node(startId,-1)); //将开始节点入队
        while(!waitSearchQueue.isEmpty()){ //队列不空
            Node currentNode = waitSearchQueue.poll(); //从队列头弹出
            System.out.println("当前目标:"+currentNode.id);
            if(currentNode.id == endId){ //如果找到了
                System.out.println("找到目标:"+currentNode.id);
                printPath(currentNode,visitedList); //打印出来路径  注意是反向的
                return;
            }
            if(visitedList.keySet().contains(currentNode.id)){ //如果搜索过的就不第二次搜索了
                continue;
            }
            //将当前节点的邻居都入队
            for(int i=0;i<this.adjList.get(currentNode.id).size();i++){
                int nodeId = this.adjList.get(currentNode.id).get(i);
                //如果访问过的就不用入队了。入队的话parentid就错了
                if(!visitedList.keySet().contains(nodeId)){
                    waitSearchQueue.offer(new Node(nodeId,currentNode.id));
                }
            }
            //标示当前节点访问过了
            visitedList.put(currentNode.id,currentNode);
        }
        System.out.println("没有路径");
    }

    //  打印出路径
    private void printPath(Node targetNode, Map<Integer, Node> visitedList){
        int parentId = targetNode.parentId;
        System.out.print(targetNode.id+"==>");
        while (parentId!=-1){
            int id = visitedList.get(parentId).id;
            parentId = visitedList.get(parentId).parentId;
            if(parentId==-1){
                System.out.print(id);
            }else{
                System.out.print(id+"==>");
            }
        }
    }

    //每一个节点的抽象   这里只存储id
    static class Node{
        private int id;
        private int parentId;
        public Node(int id,int parentId){
            this.id=id;
            this.parentId=parentId;
        }

    }

    public static void main(String[] args) {
        GraphBfs graphBfs = new GraphBfs();
        graphBfs.initialGraph();
        graphBfs.bfs(1,5);
    }
}