動態最小生成樹

習題預習

1. 如何計算Dynamic MST的權重？

2. 在動態圖中，如何快速地更新MST？

3. 如何快速查詢MST中一個特定邊的權重？

4. 在動態圖中，如何有效地保持MST中的一些性質，如最小度數？

5. 如何通過增加或刪除點來修改或計算Dynamic MST？

說明知識

Dynamic MST是指在一个图中，有一些边的权值有可能会变化，不同于静态的MST算法。因此，需要使用一种支持动态变化的数据结构来维护MST。

其中一种常见的动态MST算法是基于Kruskal算法的。它的基本思路是将原图中的边按照权值从小到大排序，然后依次加入MST中，如果加入当前边会产生环路，则跳过该边。如果某一条边的权值发生变化，则可以通过更新排序后的边集来保持MST的正确性。

例如，考虑以下图：

      1
  (0)---(1)
   |\    |
 6 |  \  | 3
   |    \|
  (2)---(3)
      2

初始时，MST为{(0,1),(0,2),(1,3)}，权值为4。如果边(0,1)的权值变为2，则在更新边集后，MST将变为{(0,1),(1,3),(0,2)}，权值为5。更新边集的过程可以使用堆来实现，从而得到较高的效率。

动态MST算法在网络的设计、优化等方面都有重要应用。

彙總重點

以下為Dynamic MST的重點：

1. 動態性：Dynamic MST是一種動態算法，它可以處理邊的插入和刪除操作，並重新計算最小生成樹。

2. 最小生成樹：Dynamic MST的目的是找到最小生成樹，即連接所有節點的最小成本。

3. Kruskal算法：Dynamic MST使用Kruskal算法來找到最小生成樹。Kruskal算法首先將邊按權值排序，然後從最小權值的邊開始添加到生成樹，直到所有節點都已連接。

4. 斷開和連接操作：Dynamic MST可以處理斷開和連接操作。如果邊被刪除，則算法會重新計算最小生成樹。如果邊被添加，則算法將判斷是否需要添加該邊並重新計算最小生成樹。

5. Eager Prim算法：另外一個用來實現動態MST的算法是Eager Prim算法。該算法也可以處理邊的插入和刪除，但相對於Kruskal算法，該算法更適用於稠密圖。

6. 複雜度：Dynamic MST的時間複雜度為O(ElogE)，其中E為邊的數目。因此，它比Prim和Kruskal算法更慢。

知識測驗

1. 有一個無向圖，每條邊有一個權值和一個時態值。時態值每一秒會增加1，當時態值等於某條邊的權值時，這條邊會消失。求出圖每秒的最小生成樹權值和。

答案：可使用Kruskal或Prim算法，但在找最小邊時要考慮時態值是否等於權值。每秒計算一次最小生成樹的權值和，逐秒累加即可。

2. 有一個有向圖，每條邊有一個權值和一個時態值。時態值每一秒會增加1，當時態值等於某條邊的權值時，這條邊會消失。求圖上每個節點到特定節點的所有路徑中，最小權值總和的最小值。

答案：先使用Dijkstra算法計算出所有節點到特定節點的最短路徑和權值。然後以最短路徑為邊建立一個新的圖，對新圖使用動態最小生成樹算法，每秒計算一次新圖上的最小生成樹權值和，逐秒累加即可。

3. 有一個無向圖，每條邊有一個權值和一個時態值。時態值每一秒會增加1，當時態值等於某條邊的權值時，這條邊會消失。求出圖每秒的最大生成樹權值和。

答案：可以先使用Kruskal或Prim算法找到最小生成樹，然後將圖上的邊權值取負，再使用Kruskal或Prim算法找到最小生成樹，最後把權值再取負即可。

4. 有一個無向圖，每個節點有一個權值和一個時態值。時態值每一秒會增加1，當時態值等於某個節點的權值時，這個節點會消失。求圖上每秒的最大生成樹權值和。

答案：可以使用Prim算法，在建最小生成樹的同時，用堆維護目前邊依據起點和終點相對大小的最大權值。每秒計算一次最大生成樹的權值和，逐秒累加即可。

5. 有一個無向圖，每條邊有一個權值和一個時態值，邊權值可能為負。時態值每一秒會增加1，當時態值等於某條邊的權值時，這條邊會消失。求圖上每秒的最小生成樹權值和和最大生成樹權值和。

答案：分別使用Kruskal和Prim算法，即可計算出每秒的最小生成樹權值和和最大生成樹權值和，其中要考慮到邊權值可能為負，所以要先把邊權值取負。