在C++中設計Prim實現的數據結構

Question

我想在C++中實現Prim的MST算法。我有一個設計問題

我實現了一個min-heap，它需要一個整數，我們可以提取min，減少key和insert-key。

現在，據我所知在Prim的我需要維護每個頂點的權重，鄰居信息。一些想法我有有：

1]定義的結構

struct node { 
    int vertex; 
    int weight; 
    int neighbor; 
}; 

使用最小堆返回以最小的重量的節點。但問題是減少鍵，因爲對於減少鍵，調用者需要通過他想要減少鍵的頂點。由於堆交換元素的次數太多，我必須通過整個列表來查找頂點，然後減少它的鍵。這是O（n），我認爲如果我這樣做，Prim會變得更糟。

2]另一種方法是維護另一個數組，它跟蹤最小堆隊列中頂點的位置。但在最小堆操作期間跟蹤位置會很麻煩。

基本上，如果我必須做reduce-key（v），如何在基於權重的min-heap隊列中找到v。那麼有沒有優雅的方式來做到這一點？哪些仍然可以保留複雜性？

Answer 1

你基本上確實需要在數據結構之間做一些交叉引用。但是，你寫

但它會很麻煩跟蹤期間最小堆操作

未唱詩班正確的位置。使用以下內容，您可以重用或編寫不需要此操作的可重用數據結構。

1. 首先，你的優先級隊列需要公開某種iterator，這使得O（1）訪問。爲此，您可以直接使用boost.Heap（請參閱下面的註釋），或從中瞭解接口的外觀。

2. 現在您使用另一個數據結構，它將映射（在O（1））節點標籤到隊列的迭代器。例如，如果節點標籤是（連續的）整數，則可以使用迭代器的vector;如果他們基本上是其他任何東西，你應該使用unordered_map。

3. 每個節點的結構也需要包括在數據結構中使用的標籤在2

項目3.意味着你需要添加以下代碼上方。

struct node { 
    ... 
    // Identifies 
    Label label; 
}; 

請注意，這是如何允許您將優先級隊列與其他數據結構分離的。當您執行decrease_key，並且您的node在優先級隊列中移動時，您不需要擔心任何事情，因爲每個節點都包含label成員。

---

說了這一切，你也應該考慮簡單的使用已經有Prim算法的Boost Graph Library。