|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 图的相关算法 >
|
|
相关知识点：5个
|
|
|
|
|
|
|
设图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条边，所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边，则必然形成回路。
|
|
|
|
图的生成树不是唯一的。从不同的顶点出发，选择不同的存储方式和遍历方式，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。
|
|
|
|
|
|
对于连通网来说，边是带权值的，生成树的各边也带权值，于是就把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法是两种常用的求最小生成树的算法。
|
|
|
|
|
|
假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从顶点集合U=｛u0｝（u0∈V）、边的集合TE=｛｝开始，重复执行下述操作：在所有u∈U，ν∈V-U的边（u，ν）∈E中找一条代价最小的边（u0，ν0），把这条边并入集合TE，同时将ν0并入集合U，直至U=V时为止。此时TE中必有n-1条边，则T=（V，｛TE｝）为N的最小生成树。
|
|
|
|
由此可知，普里姆算法构造最小生成树的过程是以一个顶点集合U=｛u0｝作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U集合直至U=V时为止。
|
|
|
|
|
|
|
|
|
|
|
|
克鲁斯卡尔求最小生成树的算法思想为：假设连通网N=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，｛｝），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。
|
|
|
|
|
|
|
|
|
|
克鲁斯卡尔算法的时间复杂度为O（eloge）（e为网中的边数），与图中的顶点数无关，因此该算法适合于求边稀疏的网的最小生成树。
|
|
|
