一种用于构造连通图的支撑树的算法

本发明涉及连通性领域以及网络的设计技术领域，公开了一种用于构造连通图的支撑树的算法；包括：获取连通图G，所述连通图G的顶点数量为n，最大度为Δ；对于G的一个顶点u，与u相邻的顶点集合记为N(u)，令N[u]＝N(u)∪{u}；而N(u)中顶点的个数称为u的度，G中所有顶点的度的最大值称为G的最大度；获取连通图G的一个顶点子集合S＝{v1,v2,…,vk}，使得对顶点子集合S中任何一个顶点vi(i≥2)，都有|N(vi)∩N(Si‑1)|≤1，这里Si‑1＝{v1,v2,…,vi‑1}；计算顶点集合S中所含的顶点数运用广度优先算法得到连通图G的一个支撑树支撑树T，从T开始，利用支撑树的变换，构造G的另一个支撑树T'，使得S中的每个顶点都是度一致顶点；具有使得T的度一致顶点尽可能多的优点。