广度优先遍历（BFS）及java代码实现

广度优先遍历（BFS）

定义及相关内容

所谓的广度优先遍历与深度优先遍历的不同就体现在“广度”这个词上，“深度优先”遍历算法讲究的是能遍历到多“深”就遍历到多深，完成了“深”的条件在来考虑“广”的条件。而“广度优先”遍历算法就恰恰相反了，“广度”优先遍历体现在一个“广”字上，即一次将某个节点所有的相邻节点都遍历完了，再去“深”度的往下遍历。（类似于层级遍历）

代码实现

/**
 *图的广度优先遍历算法 (对外公开)
 * @author SGJ
 * @param
 * @return
 */
public void broadFirstSearch(){
    isVisited=new boolean[vertexSize];
    for (int i=0;i<vertexSize;i++){
        if (!isVisited[i]){
            broadFirstSearch(i);
        }

    }
}

/**
 *（内部代码） 广度优先遍历实现
 * @author SGJ
 * @param
 * @return
 */
private void broadFirstSearch(int i){
    int u,w;
    LinkedList<Integer> que=new LinkedList( );
    System.out.println("访问到了"+i+"顶点");
    isVisited[i]=true;
    que.add( i );
    while(!que.isEmpty()){
        u=que.removeFirst().intValue();
        w=getFirstNeighbor( u );
        while(w!=-1) {
            if (!isVisited[w]) {
                System.out.println("访问到了"+w+"顶点");
                que.add( w );
                isVisited[w] = true;
            }
            w=getNextNeighbor( u,w );
        }
    }
}