帶兩種權重的MST-Kruskal算法

Question

TL，DR：當增長一個MST時，在有許多輕量級邊緣可供選擇的情況下，如何選擇一個特定的MST加入MST？

我有一個通用的問題，我一直試圖解決整個一天，但閱讀我的算法書&搜索網絡並沒有幫助我。我無法分享我的代碼，因爲這是一個大學項目，基本上是我錯過的唯一場景。

想象下面的問題。

我有一個N邊圖，我想找到它的MST（典型問題）。然而，除了具有將頂點u連接到頂點v的代價的邊緣之外，這些相同的頂點可以具有特殊的標記，使得它們可以連接到具有相同特殊標記的所有其他邊緣。

我回答了這個問題，通過創建一個特殊的頂點，與該標誌連接到的所有頂點，與相應的成本。

一切工作正常。當MST有許多可能的解決方案時會出現問題。我應該輸出一個使用最少量的特殊標誌連接。

我知道讀者可能很難在看不到我的代碼的情況下提出建議。但不幸的是，我真的無法分享。

我能說的就是我定義的邊緣，無論它是特殊或不作爲結構{U，V，成本}

有一件事我tryed，被新月順序排序的邊緣矢量按照標準kruskal算法的要求，但每當權重相同時，將「特殊邊緣」的邊緣向前推入矢量。

所以我會有這樣的東西 [成本1正常，成本1正常，成本1特殊，成本2，成本3，成本3特殊，...]。

任何意識？

感謝您的意見。

Answer 1

我認爲你正在解釋的內容似乎是正確的，但這是另一種看問題的方式。

在構建MST時，您只需比較與邊緣相關的成本 - 您的代碼無需做任何非常複雜的成本。

所以成本不一定是普通數字。他們可以有兩個組成部分，一個用於通常的比較，另一個用作第一個組分比較相等時的平局。另一種看待這種情況的方式是說，所有的成本看起來有點像123.000000000000000000000456，其中在成本的第一部分和成本的第二部分之間有如此多的零，第二部分成本在除非第一部分是平等的，並且從第二部分直到第一部分從來​​沒有任何形式的比較。

因此，在您的問題中，成本的第一部分將是邊的普通權重，如果是特殊邊，則第二部分成本爲1，否則爲0。在這種情況下，最低成本將是最低的普通成本，其中特殊邊緣的數量用作決勝手。