数据结构之生成树

生成树（Spanning Tree）从连通图的任何一个顶点出发进行遍历遍历过程中经过的边加上图的所有顶点构成的子图称为图的生成树

深度优先生成树由深度优先搜索得到的生成树简称为DFS生成树

广度优先生成树由广度优先搜索得到的生成树简称为BFS生成树

在对无向图进行遍历时对于连通图仅需从图中任一顶点出发进行深度优先搜索或广度优先搜索便可访问到图中所有顶点对非连通图则需从多个顶点出发进行搜索而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集