![在这里插入图片描述](https://img-blog.csdnimg.cn/20190406142049617.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hkVUlwcmluY2U=,size_16,color_FFFFFF,t_70)
DFS
算法是一一个递归算法,需要借助一个递归工作栈,故它的空间复杂度为
O
(
N
)
O(N)
O(N)。
遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所采用结构。
邻接表表示时,查找所有顶点的邻接点所需时间为
O
(
E
)
O(E)
O(E),访问顶点的邻接点所花时间为
O
(
N
)
O(N)
O(N),此时,总的时间复杂度为
O
(
N
+
E
)
O(N+E)
O(N+E)。
邻接矩阵表示时,查找每个顶点的邻接点所需时间为
O
(
N
)
O(N)
O(N),要查找整个矩阵,故总的时间度为
O
(
N
2
)
O(N^2)
O(N2)。