关于BST算法的时间和空间复杂性与BFS同样估计,略。 如果G是连通图,则G有生成树。注意到BFS算法中,由5~10行,将所有 邻接于顶点u但未被访问的顶点w添加到待访队列中。如果在添加w的同时将边 (u,w)收集起来,那么算法结束时,所有这些边将形成图G的一棵生成树。称为 图G的宽度优先生成树。为此,在BFS算法的第1行增加语句T=};在第7行 增加语句T=TU{(u,w)}即可 B A+D□E0 ABCDEFG A+Go B C HO 图G及其邻接链表 HLEDIEFGo 图的宽度优先搜索 图的深度优先搜索 2。图的深度优先搜索 深度优先搜索是沿着顶点的邻点一直搜索下去,直到当前被搜索的顶点不 再有未被访问的邻点为止,此时,从当前辈搜索的顶点原路返回到在它之前被搜 索的访问的顶点,并以此顶点作为当前被搜索顶点。继续这样的过程,直至不能关于 BST 算法的时间和空间复杂性与 BFS 同样估计，略。 如果 G 是连通图，则 G 有生成树。注意到 BFS 算法中，由 5～10 行，将所有 邻接于顶点 u 但未被访问的顶点 w 添加到待访队列中。如果在添加 w 的同时将边 (u,w)收集起来，那么算法结束时，所有这些边将形成图 G 的一棵生成树。称为 图 G 的宽度优先生成树。为此，在 BFS 算法的第 1 行增加语句 T={}；在第 7 行 增加语句 T=T∪{(u,w)}即可。 图 G 及其邻接链表 2。图的深度优先搜索 深度优先搜索是沿着顶点的邻点一直搜索下去，直到当前被搜索的顶点不 再有未被访问的邻点为止，此时，从当前辈搜索的顶点原路返回到在它之前被搜 索的访问的顶点，并以此顶点作为当前被搜索顶点。继续这样的过程，直至不能 B C 0 A D E 0 D E F G 0 A F G 0 C H 0 B H 0 B H 0 C H 0 A B C D E F G H A B C D E F G H 1 2 7 3 5 6 8 4 A B C D E F G H 图的深度优先搜索 1 2 3 4 5 6 7 8 A B C D E F G H 图的宽度优先搜索