Article link: Three hundred lines per day (summary)_ minfanphd blog - CSDN blog

Depth first traversal of Day34 graph

34.1 ideas

Compared with breadth first traversal, depth first traversal is depth traversal, and depth traversal is more like the first root traversal of a tree. The depth traversal is realized with the help of the stack. As shown in the figure below, starting from node a, access a first, and then put a on the stack until f can not be accessed. Then, it goes back to the previous node, looks at its lead node, then deeply traverses the lead node, and finally traverses all the nodes.

34.2 code

In the deep traversal code, the while(true) loop must have the condition to exit the loop, otherwise it will enter the dead loop.

The tempNext variable in the loop is the variable to find the node in depth. When it can't go further to the deepest point, the node goes out of the stack (stack: first in, last out) backtracking.

 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;
    }

Test 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

Test 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

In combination with yesterday's breadth first traversal, when you want to traverse the undirected graph and directed graph, you need to add a loop to check whether all nodes have been accessed. If there is no node access, you need to call the traversal method for access.

34.3 review

When traversing the tree or graph, we need to save the accessed nodes according to their structure.

Queue is used in breadth traversal

The breadth traversal of the graph can be combined with the hierarchical traversal of the tree. First, the hierarchical traversal of the tree requires traversal nodes layer by layer. When the nodes of the first layer are traversed, how to find the nodes of the second layer? The second layer is the child node of the previous layer, so the node will be saved after the first layer is accessed. The storage structure can be stack or queue. Queue (first in, first out) out of the stack is in the order from left to right, which is more in line with our reading and writing order. If we use the stack (first in, last out), the out of stack order will be very chaotic, so the hierarchy traversal uses the queue. Further, in the breadth traversal of the graph, we prefer to use queues to achieve traversal.

In depth first traversal, the stack is used.

When traversing the tree in sequence, we need to save and store the nodes after accessing the nodes. We can also choose the stack and queue. If using the queue, because the queue characteristics are first in first out, the order of entering the queue is OK, but when leaving the queue, the required nodes are at the end of the queue, and leaving the queue is the opposite. Therefore, the queue cannot meet the requirements of traversal, but the stack first in and last out is more suitable. Further, the depth traversal of our graph will first consider the stack.

The characteristics of queue and stack can be applied in many places, such as reverse printing data. When the input data enters the stack in sequence, it can be printed in reverse order. (for example, Day26:: stack implementation of binary tree depth traversal (pre order and post order))

Summary

Today, I learned the depth traversal of the graph, and combined the characteristics of breadth traversal and depth traversal back to the stack and queue.