9：图的宽度优先搜索BSF

算法描述(图邻接点表示)

 

1： 取一个节点入队

2：标记为已经访问，循环判断队列是否为空

3：不为空， 依次访问该节点的其他邻接点，如果没访问，标记已经访问，入队

4：队列为空 ，搜索完成

 

 

public class BSF {

    private boolean[] marked;

    private int count;

    private Queue<Integer> queue;

    public BSF(Graph g, int s) {
        marked=new boolean[g.V()];
        bsf(g, s);
    }

    /**
     * 宽度优先搜索
     * @param g
     * @param s
     */
    private void bsf(Graph g, int s) {
        marked[s]=true;
        queue.enqueue(s);
        count=1;
        while(!queue.isEmpty()) { // 队列不为空
            int v=queue.dequeue(); // 出队
            for(int w: g.adj(v)) { // 先访问所有的邻节点
                if(!marked[w]) {
                    count++;
                    queue.enqueue(w);
                    marked[w]=true;
                }
            }
        }
    }

 

过程请下载附件：