请输入您要查询的百科知识:
词条
普里姆算法
释义
普里姆算法
信息科学卷
普里姆算法
构造加权无向图的最小生成树的一种算法。由美国计算机科学家普里姆(Robert Clay Prim,1921— )提出。初始时,任选一个顶点u
0
加入生成树。然后选择与它关联的具有最小权值的边(u
0
,v),将顶点v加入生成树的顶点集合U中,将(u
0
,v)加入生成树的边集。以后每一步都从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u,v),将顶点v加入生成树的顶点集合U中,将边(u,v)加入生成树的边集。如此重复执行,直到图中的所有顶点都加入生成树顶点集合U中为止。若n为图中顶点的数目,则时间复杂度为O(n
2
)。较适合于求稠密图的最小生成树。
出处:信息科学卷 • 计算机科学技术 • 软件与系统
随便看
█
█
█
█
█
█
█
█
█
█
█
█
█
█
屼
█
哮吼
哮喘
哮喘性支气管炎
哮鸣音
哰
哰哰
哱
哱罗
哲
哲人
哲人之石
百科全书收录258893条中英文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。
Copyright © 2004-2023 Newdu.com All Rights Reserved
更新时间:2025/7/1 22:50:17