Javascript数据结构实践之用于邻接表表示的 Prim 的 MST 贪婪算法

Javascript实现用于邻接表表示的 Prim 的 MST 贪婪算法。问题描述 设G = (V, E)是一个无向连通带权图，即一个网络。E的每条边(v, w)的权为c[v][w]。 如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。 生成树的各边权的总和称为该生成树的耗费。 在G的所有生成树中，耗费最小的生成树称为G的最小生成树MST(minimum spanning tree) 。 算法思想 在保证连通的前提下依次选出权重较小的n – 1条边。 G=(V, E)为无向连通带权图，令V={1, 2, …, n}。 设置一个集合S ，初始化S = {1}，生成树T = Φ。 贪心策略：如果V–S中的顶点j与S中的某个点i连接, 且(i, j)是E中的权重最小的边，则选择j(将j加入S)，并将(i, j) 加入生成树T中。 重复执行贪心策略，直至V–S为空。