C++ Крускал алгоритм выдает unhandeled исключения во время выполнения

Question

Следующего код должен найти минимальный остов из матрицы смежности:

#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 

Answer 1

while (parent[i]) 
{ 
    i = parent[i]; 
} 

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

Возможно, ваша проблема связана с тем, что 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 вместо массива, его можно изменить во время выполнения, если вы столкнетесь с ситуацией, когда контейнер недостаточно велик.

Answer 2

Вы определили свой «родительский» массив размером 9 (при условии, что у вас есть максимум 9 вершин, поэтому максимальное число родителей равно 9). Шесть вершин будут работать, потому что оно меньше 9. С тринадцатью вершинами вы МОЖЕТЕ получить доступ к элементам, передавшим размер вашего родительского массива; таким образом, вы должны попытаться определить размер вашего массива в зависимости от количества вершин.

P.S В общем, вы не хотите иметь магические числа в своем коде.