日撸java 三百行 （day 22 ）图的广度优先遍历

图的广度优先遍历和数的广度优先遍历思想上几乎一模一样，都需要借助一个辅助队列，由于图可能出现非连通的情况，需要额外借助一个标记数组，将已经遍历的顶点标记。这样可以保证所有的顶点都被遍历。

今天的测试用例（非强连通图）：

以D为初始顶点：D先进队

D出队，B、C进队

B出队，A进队

C出队，A已经进过队不再进队

A出队，B、C已经进过队，不再进队，所有节点都已经遍历过，遍历完成

 代码接着昨天写：

    
    public String breadthFirstTraversal(int paraStartIntIndex,boolean flag[]){
        String resultString = "";
        int tempNodes=connectivityMatrix.getRows();
        CircleObjectQueue tempQueue=new CircleObjectQueue();
        flag[paraStartIntIndex]=true;
        resultString+=paraStartIntIndex+" ";
        tempQueue.enqueue((new Integer(paraStartIntIndex)));
        int tempIndex;
        Integer tempInteger =(Integer)tempQueue.dequeue();
        while(tempInteger!=null){
            tempIndex=tempInteger.intValue();
            for(int j=0;j 
 
运行结果：
 
 
 
 总结：图的遍历可以看做是升级版的树的遍历，大致思路都差不多，只需改变一些细节即可。由于图是由邻接矩阵表示的，所以在进行队列操作的时候就需要参考矩阵中的信息，目的是没有改变的，只是处理的手段变了。