第132页 | 算法技术手册 | 阅读 ‧ 电子书库

分析

图中的每一个顶点都会调用递归的dfs_visit函数一次。dfs_search中的循环不会执行超过n次。在dfs_visit函数中，每一个邻接顶点都要被检查，对于有向图来说，每一条边都只会遍历一次，然而在无向图中，它们会被遍历一次然后会被检查一次。在任何情况下，性能开销都是O(V+E)。