yet*_*der 6 algorithm graph-theory
假设我们给出给定图G的最小生成树T(具有n个顶点和m个边)以及我们将添加到G的权重w的新边e =(u,v).给出一个有效的算法来找到图G + e的最小生成树.您的算法应在O(n)时间运行以获得完全信用.
(c)来自Skiena手册
从u或v开始Prim或Kruskal alg,直到我们到达给定生成树路径的片段？似乎新生成树不会从一个新边缘发生很大变化.
mar*_*cog 22
确定G中新边的端点之间的路径.如果该路径中的最大长度边缘大于新边缘的最大长度边缘,请将其替换为新边缘.这在O(N)时间内运行.
资料来源:Trail Maintenance IOI 2003