DFS 学习笔记

深度优先搜索, 如果是图, 则需要记录每个节点是否被访问过, 因为图是有环的, 被访问或者已经处理过的node, 有可能在下一次其他node被访问的时候作为其child (因为有边), 再次被访问, 这样就造成了逻辑上的错误, 所以需要记录状态是否被访问过, 如果有记录, 那么dfs保证了每一条边和每一个node都只访问一次,于是时间复杂度( O( V + E ) ), 即边数加上node数量, 注意如果这个图很密 会有 E = O( V ^2) 想象一下完全连接图. 那么复杂度就变成了n方, 这大概是为什么一般说dfs会超时的原因吧.
对于结构是树的图来讲,其实不需要那个有没有被访问过的状态, 因为树的结构保证了这样的重复性不会出现, 如下图所示, 对于任何一个节点(比如1), 一旦访问完了他的所有孩子(3, 5), 那么就相当于回溯到了1 然后开始访问13的第二个child 11, 这之后再也不会出现说从另一个node访问到1, 因为这是一棵树, 是没有环的. 所以对于树而言, 复杂度是线性的O( V ), 因为 E = V – 1;

13
/ \
1 11
/ \
3 5
/ \
7 9

Written on April 7, 2013