文章链接：日撸 Java 三百行（总述）_minfanphd的博客-CSDN博客

Day34 图的深度优先遍历

34.1 思路

相比于广度优先遍历，深度优先遍历是往深度遍历，深度遍历更像是树的先根遍历。深度遍历借助栈来实现，如下图，从a节点出发，先访问a后再将a入栈，直到访问到f无法再往深度访问则是就往回溯，回溯上一个节点，看他的领接点，再对领接点进行深度遍历，最后将节点都遍历完。

34.2 代码

在深度遍历的代码中，while(true)这个循环一定要有退出循环的条件，不然会进入死循环。

在循环中的tempNext变量则是往深度找节点的变量，当往最深不能再走，则节点出栈（栈：先进后出）回溯。

 public String depthFirstTraversal(int paraStartIndex) {
        ObjectStack tempStack = new ObjectStack();
        String resultString = "";

        int tempNodes = connectivityMatrix.getRows();
        boolean[] tempVisitedArray = new boolean[tempNodes];

        //Initialize the stack
        tempVisitedArray[paraStartIndex] = true;
        resultString += paraStartIndex;
        tempStack.push(new Integer(paraStartIndex));
        System.out.println("Push " + paraStartIndex);
        System.out.println("Visited " + resultString);

        //Now visit the rest of the graph
        int tempIndex = paraStartIndex;
        int tempNext;
        Integer tempInteger;

        while (true) {
            //find an  unvisited neighbor
            tempNext = -1;
            for (int i = 0; i < tempNodes; i++) {
                if (tempVisitedArray[i]) {
                    continue;
                }

                if (connectivityMatrix.getData()[tempIndex][i] == 0){
                    continue;
                }

                //visit this one
                tempVisitedArray[i] = true;
                resultString += i;
                tempStack.push(new Integer(i));
                System.out.println("Push " + i);
                tempNext = i;

                break;
            }

            if (tempNext == -1) {
                //No unvisited neighbor. Backtracking to the last one   stored in the stack
                if (tempStack.isEmpty()) {
                    break;
                }

                tempInteger = (Integer)tempStack.pop();
                System.out.println("Pop " + tempInteger);
                tempIndex = tempInteger.intValue();
            }else {
                tempIndex = tempNext;
            }

        }

        return resultString;
    }

测试1：

This is the connectivity matrix of the graph.
[[0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 0], [0, 1, 0, 0]]
Push 0
Visited 0
Push 1
Push 3
Pop 3
Pop 1
Pop 0
Push 2
Pop 2
The depth first order of visit: 0132

 测试2：

This is the connectivity matrix of the graph.
[[0, 1, 1, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 1, 0]]
Push 0
Visited 0
Push 1
Pop 1
Pop 0
Push 2
Pop 2
The depth first order of visit: 012

 结合昨天的广度优先遍历，当对于无向图，有向图，要把图遍历完，则需要加一个循环来检查节点是否都访问完，若没有节点访问则还需要调用遍历方法进行访问。

34.3 回顾

在对树或图遍历的时候，根据他们的结构，我们都需要保存访问的节点。

在广度遍历中借助了队列

在进行图的广度遍历可以结合树的层次遍历，先说树的层次遍历，它需要一层一层的遍历节点当第一层节点遍历完了，如何找到第二层节点？第二层是上一层的孩子节点，所以第一层访问后将要将节点保存起来，选择存储的结构可以是栈或队列。队列（先进先出）出栈是从左到右的顺序，这更符合我们的读写顺序，用栈（先进后出）来实现则出栈顺序就会很混乱，所以层次遍历使用队列。进一步，在对图的广度遍历，我们更愿意借助队列来实现遍历。

在深度优先遍历借助了栈。

在对树进行先序遍历时，我们访问完节点后，需要把节点保存，存储我们也可以选择栈和队列，若使用队列，因为队列特点先进先出，进队列顺序可以，但是在出队列时需要的节点在队尾，而出队是出对头。因此队列无法达到遍历的要求，但是栈先进后出更适合。进一步我们图的深度遍历会更先弄考虑的是栈。

队列和栈特点可以在很多地方应用，例如逆向打印数据，顺序输入数据进入栈在输出时可以逆序打印。（例如Day26:: 二叉树深度遍历的栈实现 (前序和后序)）

 总结

今天学习了图的深度遍历，并结合广度遍历和深度遍历回去栈和队列的特点。