qq_38131852
nullccccccc
采纳率16.7%
2017-05-17 10:02 浏览 1.6k

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

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答 默认 最新

  • yingGe_0110 yingge_0110 2017-05-17 10:29

    举个栗子:
    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_34945661 _Kenneth 2017-05-17 14:56

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

    点赞 评论 复制链接分享

相关推荐