Графы

/*
10 17
0 4 5 3 0 0 0 0 0 0
4 0 0 0 5 0 0 0 0 0
5 0 0 0 9 5 10 0 0 0
3 0 0 0 0 7 0 8 0 0
0 5 9 0 0 0 5 0 0 14
0 0 5 7 0 0 9 4 8 0
0 0 10 0 5 9 0 0 5 8
0 0 0 8 0 4 0 0 11 0
0 0 0 0 0 8 5 11 0 3
0 0 0 0 14 0 8 0 3 0
*/
#include <iostream>
#include <ctime> //библиотека функции clock()
#include <fstream> //библиотека для работы с файлами

using namespace std;

unsigned long long compareOperations = 0, //подсчет операторов сравнения
asignmentOperations = 0; //подсчет операторов присваивания

#define INF 9999999 //число бесконечности
#define in_filename "input.txt" //названия файла входных данных
#define _x 0 //индекс под которым храниться первая вершина ребра
#define _y 1 //индекс под которым храниться вторая вершина ребра
#define _w 2 //индекс под которым храниться вес ребра

//класс Графа
class graph {
private:
    int** G; //таблиця смежности графа
    int** T; //остовное дерево
    int* parent; //массив кластеров
    int V; //количество вершин
    int U; //количество ребер
public:
    graph(string filename) {
        //открываем файл с входными данными
        ifstream in(filename);
        if (in.is_open()) {
            //если файл открыт, то вводим данные из него
            in >> V;
            in >> U;
            G = new int* [V];
            parent = new int[V];
            for (int i = 0; i < V; i++) {
                G[i] = new int[V];
                parent[i] = i;
                for (int j = 0; j < V; j++)
                    in >> G[i][j];
            }
        }
        else {
            //если файл не найден выводим соответственную ошибку
            cout << "ERROR: file not found." << endl;
            G = NULL;
        }
        T = new int* [V - 1];
        for (int i = 0; i < V - 1; i++) {
            T[i] = new int[3];
        }
    }
    //фукнция создания представления графа
    //в виде (вершина  вершина  вес)
    int** setGk() {
        int** Gk = new int* [U];
        for (int i = 0; i < U; i++)
            Gk[i] = new int[3];

        int k = 0;
        for (int i = 0; i < V; i++) {
            for (int j = i; j < V; j++) {
                if (G[i][j] != 0) {
                    Gk[k][_w] = G[i][j];
                    Gk[k][_x] = i;
                    Gk[k][_y] = j;
                    k++;
                }
            }
        }
        return Gk;
    }
    int find_set(int i);
    void union_set(int u, int v);
    void kraskal();
    void prima();
    //функция записи остовного дерева в файл
    void print() {
        if (G == NULL)
            //если дерево пустое, то завершаем выполнения функции
            return;

        ofstream out_res("result.txt", ios::app);
        out_res << "Edge :" << " Weight" << endl;
        for (int i = 0; i < V - 1; i++)
            out_res << T[i][_x] << " - " << T[i][_y] << " : " << T[i][_w] << endl;
    }
};

//функция сортирровки Gk типа записи графа в порядку возростания
//методом бульбашки
void sortGk(int** Gk, int U) {
    for (int i = 1; i < U; i++) {
        compareOperations++;
        asignmentOperations++;
        for (int j = 0; j < U - i; j++) {
            asignmentOperations++;
            compareOperations++;
            if (Gk[j][_w] > Gk[j + 1][_w]) {
                compareOperations++;
                int* tmp = Gk[j];
                Gk[j] = Gk[j + 1];
                Gk[j + 1] = tmp;
            }
        }
    }
}

//функция нахождения нужных вершин
int graph::find_set(int i) {
    if (i == parent[i]) {
        compareOperations++;
        return i;
    }
    else
        return find_set(parent[i]);
}

//функция создания кластеров
void graph::union_set(int u, int v) {
    parent[u] = parent[v];
    asignmentOperations++;
}

//алгоритм Краскала
void graph::kraskal() {
    if (G == NULL)
        //если граф пустой, то завершить выполнения функции
        return;
    //обнуляем счетчики операторов
    compareOperations = 0, asignmentOperations = 0;

    int k = 0, uRep, vRep;
    int** Gk = setGk();
    //сортируем граф для дальнейшей работы с ним
    sortGk(Gk, U);
    for (int i = 0; i < U; i++) {
        compareOperations++;
        //ищем нужные вершини
        uRep = find_set(Gk[i][_x]);
        vRep = find_set(Gk[i][_y]);
        asignmentOperations += 2;
        if (uRep != vRep) {
            //если не создается цикл,
            //то добавляем ребро в остовное дерево
            compareOperations++;
            T[k][_x] = Gk[i][_x] + 1;
            T[k][_y] = Gk[i][_y] + 1;
            T[k][_w] = Gk[i][_w];
            k++;
            asignmentOperations += 4;
            //добавляем в вершины кластер
            union_set(uRep, vRep);
        }
    }
}

//алгоритм Прима
void graph::prima() {
    if (G == NULL)
        //если граф пустой, то завершить выполнения функции
        return;
    //обнуляем счетчики операторов
    compareOperations = 0, asignmentOperations = 0;
    //массив для запоминания какие вершини мы уже прошли
    bool* selected = new bool[V]();

    int no_edge = 0; //подсчет найденых ребер
    selected[0] = true;
    asignmentOperations += 2;
    while (no_edge < V - 1) {
        /*
        Для каждой вершины в множестве S найти все смежные вершины
        вычисляем расстояние от вершины, выбранной на шаге 1.
        если вершина уже находится в множестве S, отбрасываем в противном случае
        выбираем другую вершину, ближайшую к выбранной вершине на шаге 1.
        */
        compareOperations++;
        int min = INF;
        int x = 0;
        int y = 0;
        asignmentOperations += 3;

        for (int i = 0; i < V; i++) {
            asignmentOperations++;
            compareOperations++;
            if (selected[i]) {
                compareOperations++;
                for (int j = 0; j < V; j++) {
                    compareOperations++;
                    if (!selected[j] && G[i][j]) {
                        compareOperations += 2;
                        if (min > G[i][j]) {
                            compareOperations++;
                            min = G[i][j];
                            x = i;
                            y = j;
                            asignmentOperations += 3;
                        }
                    }
                }
            }
        }

        T[no_edge][_x] = x + 1;
        T[no_edge][_y] = y + 1;
        T[no_edge][_w] = min;
        selected[y] = true;
        no_edge++;
        asignmentOperations += 5;
    }
}

int main() {
    graph g(in_filename);
    ofstream out_res;
    out_res.open("result.txt");
    out_res << "algorithm Kraskala: " << endl;
    out_res.close();
    unsigned long long Time = clock();
    g.kraskal();
    Time = clock() - Time;
    g.print();
    ofstream out_log;
    out_log.open("report.txt");
    out_log << "algorithm Kraskala: " << endl;
    out_log << "time: " << Time << "ms" << endl;
    out_log << "asignment operations: " << asignmentOperations << endl;
    out_log << "compare operations: " << compareOperations << endl;
    out_log.close();

    out_res.open("result.txt", ios::app);
    out_res << endl << "algorithm Prima: " << endl;
    out_res.close();
    Time = clock();
    g.prima();
    Time = clock() - Time;
    g.print();
    out_log.open("report.txt", ios::app);
    out_log << endl << "algorithm Prima: " << endl;
    out_log << "time: " << Time << "ms" << endl;
    out_log << "asignment operations: " << asignmentOperations << endl;
    out_log << "compare operations: " << compareOperations << endl;
    out_log.close();

    cout << "Complite! Open your file`s with result and report" << endl;
    return 0;
}