圖的廣度優先周遊概念和實作

廣度優先周遊是按層次周遊，和樹的廣度優先周遊很像。給定一個頂點，一層一層的往外周遊。可以想象成一組人在向各個方向走迷宮，當遇到路口時等待其他人走到這一層路口，然後分裂成更多的人走這個迷宮。

廣度優先周遊是通過隊列實作的。

與深度優先不同，paths找到的路徑是頂點到目标點最短的路徑

/**
 * 廣度優先周遊
 * @author yuli
 *
 */
public class BreadthFirstSearch implements Paths{
    //标記是否被通路清單
    private boolean[] marked;
    //通路的次數
    private int count;

    private int[] edgeTo;源頂點，用來記錄尋找路徑

    private int start;//開始的頂點
    public BreadthFirstSearch(UndirectedGraph graph,int start) {
        //通過頂點數建立通路清單
        marked = new boolean[graph.vertexNum()];
        this.start = start;
        edgeTo = new int[graph.vertexNum()];
        bfs(graph, start);
    }
    //廣度優先搜尋方法
    public void bfs(UndirectedGraph graph,int vertex){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(vertex);
        marked[vertex] = true;
        //如果隊列不為空就循環
        while(!queue.isEmpty()){
            //獲得隊頭
            vertex = queue.poll();
            //通路隊頭
            System.out.println(vertex);
            //周遊鄰接點
            Iterable<Integer> adj = graph.adj(vertex);
            for (Integer integer : adj) {
                //如果鄰接點沒有被通路就入隊
                if(!marked[integer]){
                    //标記鄰接點已經被通路了
                    marked[integer] = true;
                    //記錄鄰接點的源路徑
                    edgeTo[integer] = vertex;
                    //将鄰接點入隊
                    queue.offer(integer);
                }
            }
        }
    }
    /**
     * 是否包含到v的路徑
     */
    @Override
    public boolean hasPathTo(int v) {
        //該頂點是否被通路過
        return marked[v];
    }
    /**
     * 找到起始頂點到指定頂點（v）的一條路徑
     */
    @Override
    public Iterable<Integer> pathTo(int v) {
        if(!hasPathTo(v)){
            return null;
        }
        Stack<Integer> path = new Stack<>();
        //從路徑的頂點，遞歸回到開始的節點
        for(int m = v;m != start ;m = edgeTo[m]){
            path.push(m);
        }
        path.push(start);
        return path;
    }
}