優先級隊列和Prim的算法

我已經通過了C++參考手冊，並且仍然不清楚如何在STL中使用priorityqueue數據結構。優先級隊列和Prim的算法

所以，基本上我一直在嘗試使用堆來實現我自己。

我這樣做是爲了實現Prim的算法。

Vector <int, int> pq;

這是我的優先級隊列。第一個字段是節點，第二個字段是現有樹的權重。

我計劃通過更新其鄰居節點的權重，每次將新節點添加到樹中時修改pq中權重的值。

如何訪問此矢量的各個元素？我也需要能夠隨意刪除元素。

這是實現優先級隊列的好方法嗎？如果我想另一個字段添加到容器是什麼，即

Vector<int, int, int> MST

我怎麼會進入第三個元素？我想以這種方式存儲生成的MST，使得前兩個字段表示形成邊緣的頂點，以及第三個權重。

如果有人能告訴我如何使用push_back將元素分配給這個向量，它也會有所幫助。

此外，傳統的C++ STL優先級隊列是否會對此有所幫助，因爲每次將新元素添加到MST時都需要更新優先級值？當值被修改時，它會根據優先級自行糾正自己嗎？
另一個問題，這些向量，當我將它們傳遞給一個函數，並嘗試進行更改時，它是通過值傳遞還是通過引用傳遞 - 或者，這些更改是否反映在函數之外？

來源

2014-01-09 Floose

你是指古代的和過時的ARM以」 C++參考手冊「？ – PlasmaHH

如果你的'std :: vector'是'Vector'，STL向量只能有一個元素類型的模板參數（事實上它也有分配器模板參數）。您可以使用'std :: vector >'來代替您的目的。 http://www.cplusplus.com/reference/vector/vector/ – vard

@PlasmaHH：我其實是指cplusplus.com網站作爲參考。我認爲這是合法:) – Floose

在Prim的算法中，不需要隨機訪問元素。您只需跳過隊列中已連接並傳遞的元素。

所以算法如下所示：

選擇一個節點N
從N添加所有邊緣與PQ
突然從PQ
- 最低的成本優勢，如果它連接的節點它們已經在樹中，跳過它
- 否則將此邊添加到樹中，調用新節點N並回到第2點。

添加節點，只需檢查樹的大小已經size of graph - 1後。如果是的話就完成了。

請注意，PQ上的唯一操作是add_element和pop_minimum - 因此std::priority_queue將起作用。

來源

2014-01-09 14:09:11

你能解釋一下你的意思嗎？我應該怎麼做。我認爲優先隊列是最容易實現的 – Floose

我沒有寫清楚。我的意思是不需要隨機訪問。我會更新答案 –

啊好的。我不是在問隨機存取。只是如何存儲元素和檢索矢量 – Floose

首先，std::vector<int,int>無效 - 第二個類型參數是一個（可選）分配器，int不是分配器。如果您使用的是不同的底層容器，請說明它是什麼。我假設你現在想要與std::vector一起工作。

其次，std::priority_queue不支持你想要的操作（訪問和刪除任意元素），所以你不能使用它。

您可以直接使用底層的載體，和堆算法（std::make_heap等）對它進行排序：

隨機訪問就可以了（儘管目前還不清楚你期望的指標是，一旦你的載體是什麼在堆排序）
刪除任意元素將需要矢量擦除並重新運行make_heap，或者您也可以實現自己的siftDown

呵呵，第二，你可以做一些價值型的載體來存儲，如

std::vector<std::pair<int,int>>

你的第一個例子，或者更明確：

struct { 
    int node; 
    int weight; 
} Node; 
// ... 
std::vector<Node>

來源

2014-01-09 14:24:02 Useless

我將如何訪問矢量的個別元素？我也不明白分配器的作用，以及爲什麼這會使實現有效。 – Floose

@Floose你可以在（）方法或隨機訪問操作符中使用'std :: vector'，你也可以使用迭代器和原始指針來訪問向量元素。 – vard

不，因爲我在使用相同的矢量[i] .node和矢量[i] .weight？它是否正確？ – Floose

優先級隊列和Prim的算法

回答

相關問題