广度优先遍历的性质

Question

如题所述

Answer 1

与深度优先遍历类似，广度优先遍历也有许多有用的特性：
1、广度优先生成树
在广度优先遍历中，如果将每次“前进”（纵深）路过的（将被访问的）结点和边都记录下来，就得到一个子图，该子图为以出发点为根的树，称为广度优先生成树。这种情况与深度优先遍历类似。
类似地，也可以给广度优先生成树结点定义时间戳。
2、最短路径
显然，从v0出发广度优先遍历图，将得到v0到它的各个可达到的路径。我们这里定义路径上的边的数目为路径长度。与深度优先遍历不同，广度优先遍历得到的v0到各点的路径是最短路径（未考虑边权）。