“prim”算法是谁最先提出?在那篇著作里面提出来的?对现在有什么意义?有什么应用?最好详细点.谢谢

Question

“prim” 算法 是谁最先提出?在那篇著作里面提出来的?对现在有什么意义?有什么应用?最好详细点.谢谢

Answer 1

Prim算法是图论中求最小生成树的一种算法,最早于1930年由捷克数学家Vojtěch Jarník发现；并在1957年由美国计算机科学家Robert C.Prim独立发现,1959年Edsger Dijkstra再次发现了该算法,参见论文：
R.C.Prim.Shortest Connection Networks And Some Generalizations
JOSEPH B.KRUSKAL,JR.ON THE SHORTEST SPANNING SUBTREE OF A GRAPH AND THE TRAVELING SALESMAN PROBLEM
该算法用于求解图的最小生成树,所有可转换为求图的最小生成树的问题的应用均可以应用Prim算法来解决,他本人的论文里也提及了部分应用.