跳到主要导航 跳到搜索 跳到主要内容

The design and analysis of algorithm of minimum cost spanning tree

  • Xu Xusong
  • , Liu Dacheng
  • , Wu Lihua

科研成果: 期刊稿件 › 论文 › 同行评审

摘要

This paper provides a method of producing a minimum cost spanning tree (MCST) using set operations. It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm. This algorithm uses the FDG (formula to divide elements into groups) to sort (the FDG sorts a sequence of n elements in expected time O(n)) and uses the method of path compression to find and to unite. Therefore, it produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).
源语言英语
页(从-至)296-301
页数6
期刊Acta Mathematica Scientia
卷16
期3
DOI
出版状态已出版 - 1月 1996

关键词

  • A sort using the FDG
  • Algorithm analysis
  • Minimum cost spanning tree
  • Path compression
  • Set operation of find and unite

收录

  • Scopus

学术指纹

探究 'The design and analysis of algorithm of minimum cost spanning tree' 的科研主题。它们共同构成独一无二的学术指纹。

引用此