武汉理工大学 信息工程学院 数据结构 ch 图最小生成树.pptx

第7章 图;7.4.1 无向图的连通分量和生成树;D; 深度优先搜索遍历算法及广度优先搜索遍历算法中遍历图过程中历经边的集合和顶点集合一起构成连通图的极小连通子图它是连通图的一颗生成树 生成树是一个极小连通子图它含有图中全部顶点但只有n-1条边 由深度优先搜索遍历得到的生成树称为深度优先生成树由广度优先搜索遍历得到的生成树称为广度优先生成树见下页无向图G7的两种生成树;例1 画出下图的生成树;2生