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