查找MST的關鍵邊緣：可以使用修改後的Prim算法嗎？

Question

我遇到了這個問題，同時找到了一個「關鍵邊」問題的解決方案。我已經解決的原始（C++）問題是：

考慮圖G =（V，E）。查找有多少邊緣屬於全部 MST，有多少邊緣不是屬於任何 MST和有多少邊緣屬於某些MST，但不是全部。

讓我們分別在上述三種情況下分別稱爲「綠色」，「紅色」和「黃色」邊緣。

進行我的研究後，我遇到了Find all critical edges of an MST，它解決了這個問題。可以運行Kruskal算法的修改版本：如果兩個或更多相同重量的邊連接相同的組件，從而形成一個循環，那麼所有這些都是黃色的邊緣，即可以包含在MST中的邊緣（或不是） 。已被無可爭辯地選擇的邊緣是「綠色的」，並且在相同的組件中創建循環的邊緣是「紅色的」。所以，原來的問題已經解決了。

上述算法的問題在於，它運行在Kruskal算法的運行時間（如果我錯了，請糾正我）O（| E | * log | V |）。我正在考慮是否也可以使用Prim的algortihm的修改版本，因爲如果使用斐波納契堆，它具有更好的分期複雜性。（012）| | |

我的感覺是，在這裏不能使用Prim算法的修改版本，因爲我們有義務根據遞增權重迭代所有邊;但是，我無法證明這一點。那麼，是否有可能進一步降低這個問題的複雜性？

Answer 1

這個問題比最小生成樹的靈敏度分析問題更容易，這個問題是爲了確定在最小生成樹變化之前每棵樹/非樹邊緣可以增加/減少多少重量。最有名的MST靈敏度分析算法似乎是由於Seth Pettie (2005, arXived 2014)，運行時間爲O（| E | log alpha（| E |，| V |））。這非常接近最優（阿爾法是逆阿克曼），但仍然是超線性的。具有線性預期運行時間的幾種隨機算法是已知的。