普里姆算法的相关信息

发布网友 发布时间：2022-04-19 09:57

我来回答

共1个回答

热心网友 时间：2023-09-09 19:08

1）算法的基本思想：
普里姆算法的基本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。
从连通网络N = { V, E }中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集TE中，把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止。
假设G=(V，E)是一个具有n个顶点的带权无向连通图，T(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造G的最小生成树T的步骤如下：
（1）初始状态，TE为空，U={v0}，v0∈V；
（2）在所有u∈U，v∈V-U的边(u，v)∈E中找一条代价最小的边(u′，v′)并入TE，同时将v′并入U；
重复执行步骤（2）n-1次，直到U=V为止。
在普里姆算法中，为了便于在集合U和(V-U)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放顶点的序号和边的权值。　　对于每一个顶点v∈V-U，closest[v]为U中距离v最近的一个邻接点，即边(v，closest[v])是在所有与顶点v相邻、且其另一顶点j∈U的边中具有最小权值的边，其最小权值为lowcost[v]，即lowcost[v]=cost[v][closest[v]]，采用邻接表作为存储结构：
设置一个辅助数组closedge[]：
lowcost域存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；
adjvex域记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。
应用Prim算法构造最小生成树的过程: