算法_图论_深度优先遍历_非递归(Java)

1. 利用栈实现图的深度优先遍历

2. 注意，这里有个坑，操作不当可能就写成了非深度优先遍历

3. 代码中将两种情况都写了出来，看不懂的话请跟着邻接矩阵走一遍就非常易懂了

4. 两种情况输出如下：第一种是深度优先，第二种是操作不当造成的非深度优先

v0
v2
v4
v1
v3
-------无情的分割线-------
v0
v2
v4
v3
v1

5. 直接上代码

import java.util.Stack;
public class RecursionDfs {
    //初始化邻接矩阵
    static int[][] graph = {
          {0,1,1,0,0},
          {1,0,0,1,1},
          {1,0,0,1,1},
          {0,1,1,0,0},
          {0,1,1,0,0},
    };
    
    //是否访问
    static boolean[] isVisited = new boolean[5];
    
    static Stack<Integer> stack = new Stack();
    
    //主方法：我们想要利用栈来完成深度优先遍历，但是存在一种情况可能造成非深度遍历，下面有两种调用顺便解释
    public static void main(String[] args) {
        dfsOfStack();
        isVisited = new boolean[]{false, false, false, false, false};//重置是否访问
        System.out.println("-------无情的分割线-------");
        NotDfsOfStack();
    }
    
    // 栈深度优先遍历（入栈前不判断是否在栈中，重复入栈，但访问前判断是否访问，注：重复入栈保证了深度优先遍历）
    public static void dfsOfStack() {
        stack.add(0); // 遍历起始点0
        int index = 0; // 存储从栈中出栈的下标
        while(stack.size() != 0) { // 如果栈为空则遍历结束
            index = stack.pop(); // 出栈操作
            if(!isVisited[index]) { //!!!注：这里判断了是否已访问过，因为后面重复入栈了
                System.out.println("v" + index);
                isVisited[index] = true;
                for(int i = 0; i<isVisited.length; i++) {//遍历每个顶点
                    if(graph[index][i] == 1 && !isVisited[i]) {//==1表示与此顶点有连线，!isVisited[i]表示此顶点还未访问，则进行递归访问
                            stack.add(i); //!!!注：没有判断是否已在栈中，导致重复入栈
                    }
                }
            }
            
        }
    }
    
    // 栈非深度优先遍历（入栈前判断是否在栈中，不重复入栈）
    public static void NotDfsOfStack() {
        stack.add(0); // 遍历起始点0
        boolean[] marked = new boolean[5]; //是否入栈过
        int index = 0; // 存储从栈中出栈的下标
        marked[0] = true;
        while(stack.size() != 0) { // 如果栈为空则遍历结束
            index = stack.pop(); // 出栈操作
            System.out.println("v" + index);
            for(int i = 0; i<isVisited.length; i++) {//遍历每个顶点
                if(graph[index][i] == 1 && !marked[i]) {//==1表示与此顶点有连线，!isVisited[i]表示此顶点还未访问，则进行递归访问
                        stack.add(i);
                        marked[i] = true; //！！！注：入栈时将其设为访问过，不重复入栈，压在前面的元素可能就只有最后才遍历
                }
            }
        }
    }
}

代码中的无向图.png

6. 那么有没有不重复入栈的深度优先遍历呢？

貌似是没有的，因为如果栈中有前面遍历到的顶点，这次出栈的时候又遍历到了，如果不重复入栈的话，岂不是要等所有顶点遍历完才遍历最先入栈的顶点？这就造成了非深度优先遍历了。
其实，判断是否重复入栈，跟第一种方法，访问节点前先判断是否已经访问过了是差不多的运算效率。所以，不判断是否重复入栈也罢。