MST in unDirected graph
我有一个未排序的图G =（V，E）和权重函数w：E→R +。我也有G的MST T.MST in unDirected graph
我必须建立一个如下算法：
如果我们添加一个具有权重w（e'）的新边e'给E.建议一个算法它以新图G'=（V，EUe'）的MST的方式更新T.
复杂度：O（V）。
什么我建议是：
1）添加E“到T.我们得到了一个新的图形称之为T”，其中包括一个周期。
2）在T'上运行DFS并标记您访问的每个顶点。并且另外保存堆栈中的每个顶点和每个边权重
。
3）当我们访问我们已经访问的顶点时，我们停止运行。
4）并开始从栈中退出，直到我们到达我们停在的顶点。
5）在退出时，我们保存我们从 堆栈中提取的最大边缘权重。 6）如果最大边权重大于w（e'），我们将其替换。
7）否则我们保持同样的T.
我希望它很清楚。
我将非常感谢，如果任何人能够直到我，如果它的工作或给我其他
的解决方案和建议。
回答：
是你提出的解决方案是正确的，因为有相同数量的边缘节点（如T）的图由一个简单的周期与在节点的一些（也许没有）根的树这个周期。
您需要从T中删除刚好1个边，以便其余图仍然连接。显然最好的选择是删除最大的边缘。保持图形连接时可以删除的唯一边是循环中的那些边（您要添加到堆中的那些边）。
另一种解决方案是在图中找到bridges，然后找到最大的非桥边并删除它。但是，由于这是一个特殊的图形，因此您提到的解决方案会更容易（非循环边缘是循环中的边界）。
以上是 MST in unDirected graph 的全部内容， 来源链接： utcz.com/qa/257406.html
