一种构建若干棵深度和度数约束最小生成树的方法

摘要

本发明涉及网络通信技术领域，具体涉及一种以基站和Wi‑Fi接入点为根的若干棵深度和度数约束的最小生成树的生成算法，包括以下步骤：S1：以基站和Wi‑Fi接入点作为根节点，加入到生成树中；S2：在剩余服务性节点中随机选择一个节点v，从当前生成树符合深度及度数约束的节点中，选择与节点v相连边权值最小的节点u，将边(u，v)加入当前生成树；S3：循环执行S2，直至全部服务性节点加入到当前生成树，结束循环，输出以基站和Wi‑Fi接入点为根的若干棵深度和度数约束最小生成树。本发明提供了一种在给定的无向赋权图中一次能建构若干棵深度和度数约束的最小生成树的算法，能高效地为无线内容分发网络构建高质量的拓扑结构。