|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 图的相关算法 > 求最小生成树算法 >
|
|
相关知识点：2个
|
|
|
|
|
设图G=（V，E）是一个连通图，如果其子图是一棵包含G的所有顶点的树，则该子图称为G的生成树（Spanning Tree）。
|
|
|
|
当从图G中任一顶点出发遍历该图时，会将边集E（G）分为两个集合A（G）和B（G）。其中A（G）是遍历时所经过的边的集合，B（G）是遍历时未经过的边的集合。显然，G1=（V，A）是图G的子图，称子图G1为连通图G的生成树。下图所示的是图及其生成树。
|
|
|
|
|
|
|
|
对于有n个顶点的连通图，至少有n-1条边，而生成树中恰好有n-1条边，所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边，则必然形成回路。
|
|
|
|
图的生成树不是唯一的。从不同的顶点出发，选择不同的存储方式和遍历方式，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。
|
|
|
