最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 【数据结构-图(二)】图的遍历

    一、深度优先搜索(Depth First Search, DFS)

    若有N个顶点、 E条边,时间复杂度是

    • 用邻接表存储,有O(N+E)

    • 用邻接矩阵存储图,有O(N^2)

    二、广度优先搜索(Breadth First Search, BFS)

    三、连通

    • 连通:如果从VW存在一条(无向) 路径,则称VW是连通的

    • 路径VW的路径是一系列顶点{V, v1, v2, …,vn, W}的集合,其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数(如果带权,则是所有边的权重和)。如果VW之间的所有顶点都不同,则称简单路径。

    • 回路:起点等于终点的路径

    • 连通图:图中任意两顶点均连通

    • 连通分量:无向图的极大连通子图

      • 极大顶点数:再加1个顶点就不连通了

      • 极大边数:包含子图中所有顶点相连的所有边

    • 强连通:有向图中顶点VW之间存在双向路径,则称VW是强连通的

    • 强连通图:有向图中任意两顶点均强连通

    • 强连通分量:有向图的极大强连通子图

        每调用一次DFS(V),就把V所在的连通分量遍历了一遍。BFS也是一样。

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 【数据结构-图(二)】图的遍历

    1 评论

    1. 好好好

      0
      0

    发表评论

    • 52会员总数(位)
    • 321资源总数(个)
    • 20本周发布(个)
    • 2 今日发布(个)
    • 334稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情