给定旧的 MST 和新的顶点，找到最小生成树 +边缘
在示例问题中，我得到了加权图 G = (V, E) 的 MST T。问题是，如果要向图中添加一个新顶点 v 及其所有边，则使用 o(|V|log|V|) 算法来计算这个新 G* = (VU v, E*）。
到目前为止我唯一的想法是：
add min( out(v) ) to T
for each edge e in out(v) do
let u be the other vertex of e
if there exists a lower weight path from v to u then
remove all edges in that path from T
add e to T
两个问题：
- 我该如何处理可能已断开连接的顶点
- 这绝对不是 O(|V|log|V|)
我该怎么做？
In a sample problem, I'm given a MST T for a weighted graph G = (V, E). The question is, if a new vertex v and all its edges are to be added to the graph, what is an o(|V|log|V|) algorithm to compute the new MST of this new G* = (V U v, E*).
My only idea so far is:
add min( out(v) ) to T
for each edge e in out(v) do
let u be the other vertex of e
if there exists a lower weight path from v to u then
remove all edges in that path from T
add e to T
Two problems:
- What do I do with the vertices that may have gotten disconnected
- This is definitely not O(|V|log|V|)
How can I do this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您也可以在线性时间内完成此操作（如果新边的数量（例如 k）与 n 相比要少得多）。我们知道新的 MST 应该覆盖新的顶点。因此，至少必须添加一条新边。所以值最小的边必须加入MST（你可以证明这一点）；可能会发生不止一条新边发生变化。
因此，按升序对新边进行排序
将第一个添加到图表中；现在我们有一个新的周期。进行图遍历找到循环并删除该循环中具有最大值的边。
现在添加另一条新边并重复该过程。
复杂度是（n+m）乘以新添加的边数（大致线性）。
You can also do it in linear time (if the number of the new edges(say k) is considerably less comparing to n). We know new MST should cover the new vertex. So at least one of the new edges must be added. So the edge with the smallest value must be added to MST (you can prove this); it might happen that more than one new edge changes.
So sort new edges from in ascending order
Add the first one to the graph; now we have a new cycle. Doing graph traversal find the cycle and delete the edge with the maximum value from this cycle.
Now add the other new edge and repeat the procedure.
The complexity is (n+m) times the number of newly added edges(roughly linear).
最终你知道你的 MST 将位于 MST 中已有的边和添加的新边因此添加所有新边，你将得到一个图。对此进行任何正常的 MST 算法（Boruvka、Kruskal、Prims），您将得到解决方案。因为其中的边 = (V-2) 最初添加 (V-1) = 2V- 1 算法将达到您需要的时间限制。See ultimately you know that your MST will be among the edges already in th MST and the new edges addedSo add all the new edges you will get a graph. Do any normal MST algorithm (Boruvka, Kruskal, Prims) on this and you will have your solution.Since the edges in this is = (V-2) Initially (V-1) added = 2V-1 the algorithms will achieve the time bound you need.