灌水专用灌水
幼苗
共回答了21个问题采纳率:90.5% 举报
Prim算法复杂度:O(n2), 与边无关,适合求边稠密的网的最小生成树.
算法思想:假设N={V,{E}}是连通网,TE是N上最小生成树中边的集合.算法从U={u0},TE ={}开始,重复执行下述操作:在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止.
Kruskal算法复杂度:O(eloge),相对于Prim而言,适合求边稀疏的网的最小生成树.
算法思想:最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量.在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去次边而选择下一条代价最小的边.直至T中所有顶点都在同一连通分量上为止.
1年前
7