数据结构图的深度优先搜索

用邻接表存储的无向图有n个顶点,e条边,进行深度优先搜索,时间复杂度为什么是O(n+e),而不是O(n+2e)呢。

举个栗子:
n=3 e=3
表::
(0)->1->2
(1)->0->2
(2)->0->1
深度优先序列:
0 1 2 完成
1 0 2 完成
2 0 1 完成
注意:
第一种情况下从(0)进去,第一个节点是1,然后要跳到第二行的(1)再进去(1)第一个节点0,
检查发现已经访问,继续(1)的第二个节点2,然后跳到第三行的(2)再进去(2)第一个节点0,
检查发现已经访问,继续(2)的第二个节点1,检查发现已经访问,(2)节点结束。遍历完成。
所以::被读取过的顺序为:0 1 0 2 0 1
所以,时间复杂度为节点数加边数,即n+e。
另外:存在优化手段:在访问到2节点,即:0 1 0 2的时候,节点已经被全部访问完,加上节点统计,
可以省略后面的访问。
附加::深度优先搜索是一条路走到头
广度优先搜索是将所有路记录,再逐条找下一层的所有路

这里e是无向图中边的个数或者有向图中弧的个数。