• 两个算法比较
  • 空间复杂度都是O(n)

  • 时间复杂度和搜索的路径没有关系,只跟存储结构有关系

    • 邻接矩阵O(n^2)
    • 邻接表O(n+e)

      一、深度优先搜索DFS

      概念

      • 深度优先遍历

  • 用邻接矩阵表示图，遍历图当中每一个顶点都需要从头扫描，那么时间复杂度为O(n^2)

  • 用邻接表来表示图，虽然有2e个表结点，但是只需要扫描e个结点就可完成遍历O(n+e)

image.png

算法实现

1. 邻接矩阵无向图(连通图)DFS实现

  • 使用一个数组记录顶点是否被访问过

    1. int arr[]f = [0,0,0,0,0,0];

    image.png

    image.png

    2. 非连通图的遍历

    image.png

    二、广度优先搜索BFS

    从某个结点出发，依次访问该结点的邻接点，在按照这些顶点被访问的先后顺序，依次访问与他们相连接的邻接点。
    重复这个过程，知道所有顶点都被访问为止。
    image.png

    小练习

  • 下面这个非连通图当中，的广度优先搜索的次序

image.png

算法实现

image.png

效率分析

  • 如果使用邻接矩阵O(n^2)
  • 邻接表需要O(n+e )