Как оптимизировать программу и код в принципе?

Question

[NosferatuZodd]

Программа считывает данные из "1.txt", где хранится кол-во столбцов и строчек матрицы и сама матрица, далее по алгоритму Краскала программа находит минимальное остовное дерево и выводит его вес

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    ifstream file;
    int n = 0;

    file.open("1.txt");
    
    file >> n;
    vector<vector<int>> matrix(n, vector<int>(n));
    vector<int> Q(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            file >> matrix[i][j];
            if (matrix[i][j] == 0) {
                matrix[i][j] = 999; //infinity
            }
        }
    }
    file.close();

    int min = 999;
    int summ = 0;

    int mini, minj = 0;
    for (int k = 0; k < n-1; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] <= min && (Q[i] == 0 || Q[j] == 0)) {
                    min = matrix[i][j];
                    mini = i; minj = j;
                }
                else break;
            }
        }

        Q[mini] = Q[minj] = 1;
        if(min != 999) summ += min;
        cout << "{" << mini +1 << ", " << minj + 1 << "} - " << min << endl;
        min = 999;
    }
    cout << "Weight: " << summ;

    return 0;
}

Содержимое 1.txt:

6
0 5 10 14 0 0
5 0 5 6 0 0
10 5 0 7 8 9
14 6 7 0 4 0
0 0 8 4 0 12
0 0 9 0 12 0

Comments

[Евгений Шатунов]

Марк , и зачем эту программу оптимизировать? Что с ней не так?

[NosferatuZodd]

Евгений Шатунов, просто чисто ради интереса хотелось узнать, можно ли что то тут довести до идеала :)

[Евгений Шатунов]

Марк, чисто ради интереса, до идеала тут можно довести буквально все. Буквально каждую строчку. Начиная с using namespace std;, которую нужно удалить ради приближения к идеалу промышленного кода.
Оптимизация - это слишком общее слово чтобы обозначать им какой-то конкретный процесс.
Тебе стоит указать, какие именно направления оптимизации тебя интересуют.

[NosferatuZodd]

Евгений Шатунов, ну скажем например сократить код, может быть циклы как то можно упростить, а также убрать костыли по типу как "if(min != 999) summ += min;"

Answer 1

[Wataru]

Ваша реализация неправильная. Введите тест

4
0 1 2 0
1 0 0 2
2 0 0 1
0 2 1 0

Ваша программа выведет всего 2 ребра, хотя их должно быть 3. Потому что надо использовать систему непересекающихся множеств, а не массив пометок Q.

Потом, можно не искать минимальное ребро из оставшихся в цикле, а изначально отсортировать все ребра.

Посмотрите псевдокод в википедии. Или вот есть реализация.

Comments

[NosferatuZodd]

спасибо за подмеченную ошибку, даже и не знал этого

[NosferatuZodd]

сейчас проверил, все работает же, или я ошибаюсь?

[Wataru]

Марк, Это потому что я не обратил внимание на вторую ошибку. Зачем у вас там в цикле стоит else break;? Как только вы встретите первое ребро, которое не лучше текущего минимума, вы выходите из цикла.

Посмотрите на ваш вывод в этом тесте: вы там находите ребро длины 1, потом 2, потом снова 1 - это все-равно неверно. Алгоритм Крускала должен находить ребра в порядке увеличения длины.