Visual Studio 2013 — Алгоритм C ++ Kruskal выдает необработанное исключение во время выполнения
Следующий код должен найти минимальное остовное дерево из матрицы смежности:
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <conio.h>
#include <vector>
#include <string>
using namespace std;
int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];
int find(int);
int uni(int, int);
int find(int i)
{
while (parent[i]) // Error occurs at this line
i = parent[i];
return i;
}
int uni(int i, int j)
{
if (i != j)
{
parent[j] = i;
return 1;
}
return 0;
}
int main()
{
cout << "MST Kruskal:\n=================================\n";
cout << "\nNo. of vertices: ";
cin >> n;
cout << "\nAdjacency matrix:\n\n";
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
cin >> cost[i][j];
if (cost[i][j] == 0)
cost[i][j] = 999;
}
}
cout << "\nMST Edge:\n\n";
while (ne < n)
{
for (i = 1, min = 999; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (cost[i][j] < min)
{
min = cost[i][j];
a = u = i;
b = v = j;
}
}
}
u = find(u);
v = find(v);
if (uni(u, v))
{
cout << ne++ << "th" << " edge " << "(" << a << "," << b << ")" << " = " << min << endl;
mincost += min;
}
cost[a][b] = cost[b][a] = 999;
}
cout << "\nMinimum cost = " << mincost << "\n" << endl;
system("PAUSE");
return 0;
}
Работает для 6-ти вершин и следующей матрицы:
0 3 1 6 0 0
3 0 5 0 3 0
1 5 0 5 6 4
6 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0
однако для 13 вершин и со следующей матрицей:
0 1 0 0 0 2 6 0 0 0 0 0 0
1 0 1 2 4 0 0 0 0 0 0 0 0
0 1 0 0 4 0 0 0 0 0 0 0 0
0 2 0 0 2 1 0 0 0 0 0 0 0
0 4 4 2 0 2 1 0 0 0 0 4 0
2 0 0 1 2 0 0 0 0 0 0 2 0
6 0 0 0 1 0 0 3 0 1 0 5 0
0 0 0 0 0 0 3 0 2 0 0 0 0
0 0 0 0 0 0 0 2 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0 1 3 2
0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 4 2 5 0 0 3 0 0 1
0 0 0 0 0 0 0 0 0 2 0 1 0
эта ошибка происходит:
Unhandled exception at 0x00ED5811 in KruskalMST.exe: 0xC0000005: Access violation reading location 0x00F67A1C.
Ошибка возникает в строке 17: while (parent[i])
VS Autos:
Name Value Type
i 138596 int
parent 0x00ee048c {2, 999, 999, 999, 999, 999, 999, 999, 2} int[9]
[0] 2 int
[1] 999 int
[2] 999 int
[3] 999 int
[4] 999 int
[5] 999 int
[6] 999 int
[7] 999 int
[8] 2 int
Решение
Вы определили, что ваш родительский массив имеет размер 9 (при условии, что у вас максимум 9 вершин, поэтому максимальное количество родителей равно 9). Шесть вершин будут работать, потому что их меньше 9. С тринадцатью вершинами вы МОЖЕТЕ получить доступ к элементам, превышающим размер родительского массива; Таким образом, вы должны попытаться определить размер вашего массива в зависимости от количества вершин.
P.S В общем, вы не хотите иметь магические числа в вашем коде.
Другие решения
while (parent[i])
{
i = parent[i];
}
Прежде всего, пожалуйста, используйте фигурные скобки, чтобы заключить оператор while. Любое добавление другой строки может вызвать нежелательное поведение.
Ваша проблема, вероятно, в том, что parent[i] присваивает значение i что находится за пределами parent массив.
Попробуйте это, чтобы увидеть, что он назначает i:
while (parent[i] != 0)
{
cout << "parent[i] is " << parent[i];
i = parent[i];
}
Поскольку родительский массив имеет размер 9, если i когда-либо установлен на 9 или больше (или меньше 0, как-то), вы можете получить нарушение доступа при использовании parent[i],
Несвязанный: хорошо, чтобы быть ясным о том, какое условие вы проверяете в while, Прежде чем я увидел это parent был int [], я не знал, может ли это быть массив указателей или логических, я не знал, что while условие проверял.
Если вы хотите быть в безопасности, пожалуйста, проверьте ваш parent массив:
static const int parentSize = 9;
int parent[parentSize];
while (parent[i] != 0 && i > 0 && i < parentSize)
{
cout << "parent[i] is " << parent[i];
i = parent[i];
}
Вероятно, вам нужно увеличить parentSize до чего-то большего. Если вы хотите что-то более динамичное, вы можете рассмотреть возможность использования std :: vector вместо массива, его размер можно изменить во время выполнения, если вы столкнетесь с ситуацией, когда контейнер недостаточно велик.