Prim的算法C++

Question

我正在C++中實現一個簡單版本的Prim算法，並且有一些難度將算法轉化爲與我非常基本的圖形實現一起工作。

我有邊緣的結構，如下所示：

struct edge 
{ 
    int src; 
    int dest; 
    int weight; 
}; 

我簡單地推邊緣以在該圖類的載體。我不知道這是否是實現Prim的最好方法，但它似乎對我的最終結果是最佳的，因爲它能夠簡單地打印出頂點的數量visitTed和最小生成樹的總重量。

我想我明白普里姆的基本想法，但我有幾點疑問。我所要求的只是朝着正確的方向前進。特定於我的用法的僞代碼將是理想的。

1）選擇一個起始頂點

2）在從源頂點到所有其他while循環中，添加邊緣權重以某種形式的堆（這是混淆對我來說，一些算法說來初始化到無限但STL優先級隊列沒有備用方法......）

3）獲取最低優先級（從優先級隊列中彈出或者在我糟糕的執行過程中遍歷最低值的向量）

4）如果最低值的目標已被訪問，把那個邊緣，距離嘗試下。如果不是，則將該邊添加到最小生成樹並將其標記爲已訪問。

我沒有太多的代碼和我得到收益遞減點，所以任何建議表示讚賞。這是我得到的：

vector<edge> graph::prims(int source, vector<edge> vt) 
{ 
    int current; 
    vector<bool> visited(numVert, false); 
    vector<unsigned int> minWeight; 
    minWeight.reserve(numVert); 

    // Intilize minWeight to a large number 
    for(int j=0; j < numEdges; j++) 
    { 
     minWeight[j] = 0xffffffff; 
    } 

    current = source; 

    // Will this even work? What if I pick the nth node... 
    while (current <= numEdges) 
    { 
     // This should add the edge weights to the current vertex 
     // to a vector so the minimum can be found 
     for(int i = 0; i < numVert; i++) 
     { 
      if(vt[i].src == current && visted[i] == false) 
      { 
       minWeight.push_back(vt[i].weight); 
      } 
     } 
    } 

    // Need to finish Prim's 


    return vt; 
} 

我一直在試圖從互聯網上獲取代碼並修改整天，並且它讓我無處可去。所以我最終決定自己嘗試一下。這不是很多，但這個我花了大約兩個小時......

我的代碼可以在Google Drive找到。

Answer 1

我已經通過您的代碼一看，這似乎是你的設計是在某些領域不完整的。讓我們來看看。

你類看起來是這樣的：

class graph { 
public: 
     ... function prototypes ... 
private: 
     int numVert; 
     int numEdges; 
}; 

此類聲明是丟失了一些比較重要的信息：特別是，當存儲頂點的數量和邊緣的數量，沒有關於頂點信息或屬於給定實例的邊緣曾經存儲。

您已經有edge和city結構可分別用於邊和頂點。這些可以存儲在您的類的std::vector<...>成員中，並且 - 如果您仔細保留相關排序，則可以通過數字索引解決這些問題，並且可以（大部分）很好。完成之後，您可以調整addEdge和addCity，以便它們實際上做他們應該做的事情 - 也就是分別向邊緣或頂點添加邊緣或頂點到實例。

另一件需要考慮的事情是如何實際存儲邊緣。'最好'的方法取決於問題的性質，但是對於大多數應用程序來說，只需將邊緣存儲在由頂點ID（例如std::map<std::vector<...> >實例）鍵控的結構中，或者作爲每個頂點對象中的子場（例如通過添加一個std::vector<...>會員字段到您的city類）。

---

這一邊，讓我們來談談你正試圖實現的實際算法。

Prim算法是，在它的心臟，這個迭代規則的應用：

添加到候選最小生成樹的最小重量邊樹裏面的一些頂點與頂點一些外面。

也就是說，在每一步，我們這樣做：

• 考慮到目前爲止，我們已經建立了樹的頂點;稱這個集合爲A.（最開始，這是你選擇的單個頂點，最後，這是包含初始頂點的連通組件的頂點集合;如果連接了圖形，則這是所有頂點。 ）
• 考慮我們圖中不在樹中的頂點;將該集合稱爲B.
• 查看將集合A中的任何頂點與集合B中的任何頂點（以圖形理論語言，圖形的切割（A，B）的切割集合）連接的所有可能邊。如果沒有，你就完成了。否則，選擇最小權重的邊緣並將其添加到樹中。

您可以證明，如果連接了原始圖，該算法將生成一個具有最小總邊權重的生成樹。試着向你自己證明這一點。

---

那麼，你現在在哪裏？雖然我無法理解你的想法，但我可以告訴你你的代碼告訴我什麼：

• 你試圖跟蹤你已經訪問的頂點集。
  • 這很好;你需要那個。
• 您正試圖跟蹤剪切集合，即退出訪問集合的邊緣。
  • 你也需要這個。
  • 我不確定爲什麼你只用std::vector<unsigned int>來達到這個目的，因爲對於一個給定的邊，你需要跟蹤三個數量：'from'頂點，'to'頂點和權重。您可能需要一個std::vector<edge>來代替此目的。
• 它看起來像你試圖填充這個集合。
  • 根據是否更改數據結構的佈局，您可能需要重做此位。
  • 主要思想 - 找到從訪問節點到未訪問節點的邊緣 - 是否存在，但我不確定當前代碼建議的方法是否有效。

那麼，什麼是從算法失蹤？

• 一旦你有一個有效的cut-set，你需要找到權重最低的集合中的邊緣。
• 您需要將此邊添加到返回集。
• 您需要將此邊連接的頂點標記爲已訪問。調用此節點N.
• 您需要更新剪切集。特別是，連接N到先前訪問的頂點的任何邊都需要被移除，並且需要添加將N連接到某個未訪問頂點的任何邊。

---

我希望這可以幫助你。如果您對任何事情感到困惑，需要更多解釋，或者認爲我所說的內容不準確或不正確，請告訴我，我會更新此答案。

Answer 2

//Prims Algorithm implementation using matrix in simpler way 

#include<iostream> 
#include<limits.h> 
using namespace std; 
int n=5; 

//Min Node will return the node having minimum weight 
int min_node(int matrix[5][5],bool visited[5]){ 
    int result; 
    int min_value=INT_MAX; 

    for(int i=0;i<n;i++){ 
     if(visited[i]){ 
      for(int j=0;j<n;j++){ 
       if(matrix[i][j]<min_value && !visited[j]){//If the node is not in visited array then consider it,otherwise not, 
                  //to avoid the loop in the minimum spanning tree 
        min_value=matrix[i][j];//update the min value 
        result=i*10 + j; 
       }//endl inner if structure 
      }//end inner for loop 
     }//end outer if structure 
    }//end outer for loop 

    return result; 
} 

int main(){ 
cout<<"Hello world\n"; 
int matrix[5][5]={ 
        {0,18,15,0,0}, 
        {18,0,12,0,13}, 
        {15,12,0,20,0}, 
        {0,0,20,0,11}, 
        {0,13,0,11,0} 
       }; 

//Display the matrix 
for(int i=0;i<n;i++){ 
    for(int j=0;j<n;j++) 
     cout<<matrix[i][j]<<"\t"; 
    cout<<"\n"; 
} 

//Make the disconnected node weight = MAX 
for(int i=0;i<n;i++){ 
    for(int j=0;j<n;j++){ 
     if(matrix[i][j]==0) 
      matrix[i][j]=INT_MAX; 
    } 
} 

//Take an visited array 
bool visited[5]; 
//Make all the entries of visited array false 
for(int i=0;i<5;i++) 
    visited[i]=false; 

int source; 
cout<<"Enter the source vertex\n"; 
cin>>source; 

visited[source]=true; 

//Tree having 'n' vertices will have 'n-1' edges in the minimum spanning tree 
int t=4; 
while(t>0){ 
    int result=min_node(matrix,visited); 
    int i=result/10; 
    int j=result%10; 
    visited[j]=true;//Now add the new node the visited, to consider the its edeges in the condition 
    cout<<"Path "<<i<<"- "<<j<<" ="<<matrix[i][j]<<endl; 

t--; 
} 

return 0; 
}