Алгоритм простых чисел: ошибка во время выполнения (C ++) - PullRequest
Новая
       64

Алгоритм простых чисел: ошибка во время выполнения (C ++)

0 голосов
/ 27 мая 2018

Я пытался реализовать алгоритм самостоятельно, но я получаю ошибку времени выполнения при выполнении, и я совершенно не могу понять, почему.

Код разбит на три части: A) СохранениеГраф в форме матрицы смежности, где ячейка (i, j), если 0 представляет, ребро отсутствует, между двумя вершинами, где, если ненулевая запись, означает наличие ребра, а запись равна весу ребраот i до j.

B) Создание 3-х массивов для хранения весов, родителей и отслеживания посещенных вершин, и в цикле First while построения MST я вызываю функцию getMin, чтобы предоставить мне минимумвес среди непосещенных ребер, затем я обновляю веса соответствующих соседей, если они ниже, чем их ранее назначенные веса, и продолжаю его до тех пор, пока счетчик i не станет равным n.

C) Последний шаграспечатать MST, что довольно просто.

Вот код: 

#include<iostream>
#include<climits>
using namespace std;

int getMin(int* weights, int n, bool* visited) {
    int minimum = INT_MAX;
    int minIndex = -1;
    for(int i = 0; i < n; i++) {
        if(weights[i] < minimum && !visited[i]) {
            minimum = weights[i];
            minIndex = i;
        }
    }
    return minIndex;
}

int main() {
    int n, e;
    cin >> n >> e;
    //Creating an adjacency matrix to store Graph
    int** edges = new int*[n];
    for(int i = 0; i < n; i++) {
        edges[i] = new int[n];
        for(int j = 0; j < n; j++) {
            //Initializing each entry as 0(False) for now
            edges[i][j] = 0;
        }
    }
    //Taking input of edges
    for(int i = 0; i < e; i++) {
        int f,s,w;
        cin >> f >> s >> w;
        edges[f][s] = edges[s][f] = w; //Storing weights as the entries
    }

    //Array 1 for tracking the visited vertices
    bool* visited = new bool[n];
    for(int i = 0; i < n; i++) {
        visited[i] = false;
    }
    //Array 2 for maintaining weights
    int* weights = new int[n];
    for(int i = 0; i < n; i++) {
        if(i == 0) {
            //Treating 0 as source vertex
            weights[i] = 0;
        }
        else {
            weights[i] = INT_MAX;
        }
    }
    //Array 3 for maintaining parents of each vertex
    //Will be helpful in tracing the MST after n - 1 edges are added
    int* parent = new int[n];
    for(int i = 0; i < n; i++) {
        if(i == 0) {
            //Source vertex has no parent
            parent[i] = -1;
        }
        else {
            //INT_MIN symbolizing no parents yet
            parent[i] = INT_MIN;
        }
    }
    //Building the MST
    int i = 0;
    while(i < n) {
        int minimum = getMin(weights, n, visited);
        visited[minimum] = true;
        for(int j = 0; j < n; j++) {
            if(edges[minimum][j] != 0 && !visited[j]) {
                if(edges[minimum][j] < weights[j]) {
                    weights[j] = edges[minimum][j];
                    parent[j] = minimum;
                }
            }
        }
        i++;
    }
    //Printing the MST
    int k = 0;
    while(k < n) {
        for(int j = 0; j < n; j++) {
            if(parent[j] == k) {
                cout << k << " " << j << " " << edges[i][j] << endl;
            }
        }
        k++;
    }
    return 0;
}
...