Алгоритм Прима по вектору & lt; Vector & lt; int & gt; & gt; В результате SegFault

У меня есть следующие 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

Я предполагаю, что важно отметить, что мой код пытается найти грани минимального остовного дерева в графе, используя алгоритм Прима.

0

Решение

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 для большей безопасности.

1

Другие решения

Одна ошибка в том, что вы используете станд :: вектор :: резерв () вместо станд :: вектор :: размер ().

Этот раздел кода обращается к вектору с индексом вне границ, так как 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).

0

По вопросам рекламы [email protected]