基于优先队列的最小生成树算法

An Algorithm Based on Priority Queue for Producing Minimum Spanning Tree

本文提出一个获取连通网络是小生成树的算法。该算法采用一个优先队列组织各顶点集合，每次根据边的权值对队列头集合进行增长。由于对每个顶点的相关联边进行了按权值分级排序的预处理，算法获取具有。个预示e条边的无向连通网络的最小生成树的期望时间是O（e*loglogn）。

An algorithm fOr producing minimum spanning trees of undirected networks is provided. A priority queue is used to organize sets of nodes, and the head set of the queue is always grown in accordance with the edge weights. Since the edges are sotted according to weights beforehand, the minimum spannins tree of an undirected network with n nodes and e edges can be computed in expected time O (e * loglogn)