›› 1983, Vol. 9 ›› Issue (01): 15-29.
• 论文 • 上一篇 下一篇
霍义兴,谈明
发布日期:
Published:
摘要： 本文给出在任意有向图中求必经结点的一个算法,以及对应的BASIC语言写的程序。算法使用了深度优先搜索、脱机最小值算法、不相交集的合并算法,以及能体现优先队列功能的2—3树算法,从而使算法的时间复杂性最多为O(nlogn+e),空间复杂性最多为O(e),n,e分别为图的结点数和边数。当e≥nlogn时,本算法时间复杂性为O(e),它在一个常数范围内是最优的。
霍义兴,谈明. 求有向图必经结点的一个有效算法[J]. , 1983, 9(01): 15-29.
/ 推荐 / 导出引用
链接本文: https://www.ecice06.com/CN/Y1983/V9/I01/15