美文网首页
数据结构笔记(图-图的遍历)

数据结构笔记(图-图的遍历)

作者: 岸边露伴一动不动 | 来源:发表于2020-07-12 17:51 被阅读0次

    深度优先搜索(Depth First Search,DFS):
    相当于树的先序遍历
    用邻接表存储,则DFS的时间复杂度为O(N+E)
    用邻接矩阵存储,则DFS的时间复杂度为O(N^2)

    广度优先搜索(Breadth First Search,BFS):
    相当于树的层序遍历
    利用队列实现,从第一个点开始,压入队列,弹出该点时,将所有与该顶点直接关联的点压入队列,以此类推
    时间复杂度同DFS

    连通:如果从V到W存在一条(无向)路径,则认为V和W是连通的
    路径:V和W的路径是一系列顶点的集合,路径的长度是路径的边数(带全,则是所有边的权重和)
    简单路径:V和W路径的所有顶点都不同
    回路:起点等于终点的路径
    连通图:图中任意两个顶点都连通
    连通分量:无向图的极大连通子图
    1、极大顶点数:再加一个顶点就不连通了
    2、极大边数:包含子图中,所有顶点相连的所有边
    强连通:有向图中,V和W之间存在双向路径
    强连通图:有向图中任意两顶点均强连通
    强连通分量:有向图的极大强连通子图

    遍历不连通的图:
    遍历图的顶点,如果未被访问过,则调用DFS或BFS来进行访问

    Q:一个顶点算不算连通分量?yes

    例:007跳🐊问题
    六度空间理论

    相关文章

      网友评论

          本文标题:数据结构笔记(图-图的遍历)

          本文链接:https://www.haomeiwen.com/subject/xuhncktx.html