求助大佬们，为什么u是v的祖先，则在dfs中结束时间u大于v

是不是因为在一个有向无环图中，存在u一直往下寻找然后可能需要回退寻找别的节点是否有继续往下深度搜索的可能

？

图的深度优先在230面，思想是递归，所以需要用到递归调用栈，栈的原理是后进先出

递归调用栈，先将每个结点所有的子孙结点访问完成，辅助数组全为true，再入栈，大白话就是在最深处开始入栈，所以辈分最小的子孙结点先入栈先被访问

入栈看作真正的DFS访问，深度搜索的过程只改变辅助数组，辅助数组的意义是标记这个结点是否被遍历过，即false是没有被遍历，true是被遍历了，太抽象了，不好描述，你悟一下，有不懂的再回我就行

下载贴吧APP
看高清直播、视频！

分享到: