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

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

2个回答

举个栗子:
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的时候,节点已经被全部访问完,加上节点统计,
可以省略后面的访问。
附加::深度优先搜索是一条路走到头
广度优先搜索是将所有路记录,再逐条找下一层的所有路

qq_38131852
nullccccccc 每个顶点访问一次,每条边查找一次,无向图存了2e条边,所以查找2e次,即使访问过了,不是也要查找吗?所以不应该是n+2e吗?
大约 3 年之前 回复

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

qq_38131852
nullccccccc 对啊,如果e是无向图边的个数,那么边不就被存了2遍吗,所以不是2e吗?
大约 3 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐