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

深度优先遍历可以借用一个辅助栈：

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

首先选取顶点D为初始顶点：

接着根据邻接矩阵的信息把E压栈：

由于D已经被访问过，并且E没有与其余节点相连接，将E出栈，D同理：

 等D出栈后，队列为空，但是标记数组显示还有顶点未被访问，则程序接着运行：

 代码及运行效果：

    
    public String depthFirstTraversal(int paraStartIndex,boolean flag[]){
        ObjectStack tempStack=new ObjectStack();
        String resultString="";
        int tempNumNodes=connectivityMatrix.getRows();
        flag[paraStartIndex]=true;
        resultString+=paraStartIndex+" ";
        tempStack.push(paraStartIndex);
        int tempIndex=paraStartIndex;
        int tempNext;
        Integer tempInteger;
        while (true){
           tempNext=-1;
           for(int i=0;i 
 
 
 
 
 
 
 总结：广度优先用队列，深度优先使用栈，需要注意的是一旦找到与当前顶点连通的顶点后就得break当前循环。