广度优先搜索(BFS)和深度优先搜索(DFS)

1、广度优先搜索(BFS):

  a、类似于二叉树的层次遍历。

  b、适用于无权图或者权值相等的单源最短路径。

  c、利用到队列

复杂度分析:

广度优先搜索(BFS)和深度优先搜索(DFS)

2、广度优先生成树:

  如果图是由邻接矩阵存储的,则其BFS生成树是唯一的,如果用邻接表存储则不唯一。

3、深度优先搜索(DFS):

  a、类似于树的先序遍历

  b、利用到栈

复杂度分析:

广度优先搜索(BFS)和深度优先搜索(DFS)

4、深度优先的生成树和生成森林

  a、对连通图调用DFS才可以生成树,非连通则生成森林。

  b、邻接矩阵存储的图,生成树唯一,邻接矩阵存储的图,生成树不唯一。