プリム法>私は、次の3つの機能を持っているセグメンテーション違反

Question

その結果：

int minKey(vector<int> key, vector<bool> mstSet){ 
    int min = INT_MAX; 
    int min_index; 
    for (int i = 0; i<elements2D.size(); i++){ 
     if (mstSet[i] == false && key[i] < min){ 
      min = key[i]; 
      min_index = i; 
     } 
    } 
    return min_index; 
} 

int printMST(vector<int> parent, int n, vector<vector<int>> graph){ 
    cout << "edges: " << endl; 
    for (int i = 1; i<graph.size(); i++){ 
     cout << parent[i] << " " << i << endl; 
    } 
} 

void primMST(vector<vector<int>> graph){ 
    vector<int> parent; 
    parent.reserve(graph.size()); 
    vector<int> key; 
    key.reserve(graph.size()); 
    vector<bool> mstSet; 
    mstSet.reserve(graph.size()); 

    for (int i = 0; i<graph.size(); i++){ 
     key[i] = INT_MAX; 
     mstSet[i] = false; 
    } 

    key[0] = 0; 
    parent[0] = -1; 

    for (int count = 0; count<graph.size()-1; count++){ 
     int u = minKey(key, mstSet); 
     mstSet[u] = true; 
     for (int v = 0; v < graph.size(); v++){ 
      if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]){ 
       parent[v] = u; 
       key[v] = graph[u][v]; 
      } 
     } 
    } 
    printMST(parent, graph.size(), graph); 
} 

そして、私のメインの機能では、私はこのようにそれを呼び出す：

primMST(elements2D); //elements2D is my adjacency matrix 

しかし、それは常に返します。セグメンテーション違反。デバッグを使用することで、どこで発生するのかがわかりましたが、状況をどのように修正するかはわかりません。

int u = minKey(key, mstSet) 

それはセグメンテーションフォルトで結果：

だから基本的に、私は私が言ったときにことを考え出しました。だから私はそれを関数に追いつけ、キー[i]は機能していないことを発見しました。それについての何かが、結果をセグメンテーションとして出力し続けます。誰かが私がこれを解決するのを助けることができれば、それは非常に感謝するだろう

いくつかの重要な情報：

elements2Dは次のようになります。

0 2 6 0 0 0 0 3 
2 0 0 0 4 0 0 1 
6 0 0 0 3 0 0 2 
0 0 0 0 0 0 0 0 
0 4 3 0 0 0 0 0 
0 0 0 0 0 0 7 0 
0 0 0 0 0 7 0 0 
3 1 2 0 0 0 0 0 

出力は次のようになります。

edges: 
0 1 
1 7 
2 7 
2 4 
5 6 

私は私のコードをしようとしていることに注意することが重要であると思いますPrimのアルゴリズムを使用してグラフ内の最小全域木の辺を見つける。

Answer 1

int minKey(vector<int> key, vector<bool> mstSet){ 
    int minKey(vector<int> key, vector<bool> mstSet){ 
    int min = INT_MAX; 
    int min_index; // NOT INITIALIZED! 
    for (int i = 0; i<elements2D.size(); i++){ // What is elements2D? 
     if (mstSet[i] == false && key[i] < min){ // What if the two vectors are different sizes? 
      min = key[i]; 
      min_index = i; 
     } 
    } 
    return min_index; 
} 

この機能にはいくつかの問題があります。 min_indexは初期化されません。 forループが何も実行されない場合、返されるのは何ですか？また、elements2Dはどこに定義されていますか？あなたはkeyとmstSetを繰り返しているようです。それらのサイズが同じであることを確認するか、より良い方法として、std::vector<std::pair<int, bool>>を使用してください。

添字演算子std::vectorは、境界チェックを実行しません。安全性を高めるためにatを使用してください。

Answer 2

間違いの1つはstd::vector::resize()の代わりにstd::vector::reserve()を使用していることです。

reserve()は要素を作成しないため、このセクションのコードでは範囲外インデックスを持つベクトルにアクセスします。

void primMST(vector<vector<int>> graph){ 
    vector<int> parent; 
    parent.reserve(graph.size()); 
    vector<int> key; 
    key.reserve(graph.size()); 
    vector<bool> mstSet; 
    mstSet.reserve(graph.size()); 

    for (int i = 0; i<graph.size(); i++){ 
     key[i] = INT_MAX; // <-- out of bounds access 
     mstSet[i] = false; // <-- out of bounds access 
    } 

修正は、それが実際のベクトルのエントリを作成するように、いずれかstd::resize()を使用するか、必要なサイズのベクターを構築することです。

void primMST(vector<vector<int>> graph){ 
    vector<int> parent(graph.size()); 
    vector<int> key(graph.size(), INT_MAX); 
    vector<bool> mstSet(graph.size()); 

keyとmstSetのコンストラクタは、コンストラクタの2番目のパラメータで指定された値とのベクトルを初期化する（またはvector<bool>の場合、値はfalseに設定されているので、後続forループは、必要ではありません）。