У меня есть следующие 3 функции:
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)
это приводит к segfault. Итак, я последовал за этим в функцию и обнаружил, что ключ [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
Я предполагаю, что важно отметить, что мой код пытается найти грани минимального остовного дерева в графе, используя алгоритм Прима.
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
для большей безопасности.
Одна ошибка в том, что вы используете станд :: вектор :: резерв () вместо станд :: вектор :: размер ().
Этот раздел кода обращается к вектору с индексом вне границ, так как 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());
Последующее for
цикл не является необходимым, так как конструктор для key
а также mstSet
инициализирует вектор значениями, указанными во втором параметре конструктора (или в случае vector<bool>
, значения установлены в false
).