3 лаба

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

//Класс для представления графа с помощью матрицы смежности:
class MGraph
{
    int vernum; //число вершин
    bool oriented; //true - ориентированный; false - неориентированный
    bool** matrix; //матрица смежности
    int comptotal = 0; //число компонент
    int zmax, //максимальное число цветов, используемых на текущем шаге
        zcur, //число различных цветов в Pcur на текущем шаге
        zmin, //число различных цаетов в Pmin
        * Pmin, //текущая минимальная раскраска
        * Pcur;// текущая раскраска
public:
    //конструктор
    MGraph(int vrnum, bool orient)
    {
        vernum = vrnum;
        oriented = orient;
        matrix = new bool* [vrnum];
        for (int i = 0; i < vrnum; i++)
            matrix[i] = new bool[vrnum];
        for (int i = 0; i < vrnum; i++)
        {
            for (int j = 0; j < vrnum; j++)
                matrix[i][j] = false;
        }
    }
    //деструктор
    ~MGraph()
    {
        for (int i = 0; i < vernum; i++)
        {
            delete[] matrix[i];
        }
        delete[] matrix;
    }
    int getvernum() //получить число вершин
    {
        return vernum;
    }
    bool getmatrix(int a, int b) // получить матрицу смежности
    {
        return matrix[a][b];
    }
//задаем ребра дуги
    void setedge(int a, int b)
    {
        if (a < 0 || a >= vernum) return;
        if (b < 0 || b >= vernum) return;
        matrix[a][b] = true;
        if (!oriented) matrix[b][a] = true;
    }

    void removeedge(int a, int b)
    {
        if (a < 0) return;
        if (b < 0) return;
        matrix[a][b] = false;
        if (!oriented) matrix[b][a] = false;
    }
//методы для выделения компонент
    void cdeep(int cver, int* R)
    {
        R[cver] = this->comptotal;
        for (int i = 0; i < vernum; i++)
            if (matrix[cver][i] && !R[i])
                cdeep(i, R);
    }
    int* getcomp()
    {
        int i, * R = new int[vernum];
        for (i = 0; i < vernum; i++)
            R[i] = 0;
        for (i = 0; i < vernum; i++)
            if (!R[i])
            {
                this->comptotal = this->comptotal++;
                cdeep(i, R);
            }
        return R;
    }
/*cver – текущая проверяемая вершина,
R – массив номеров в порядке обхода (R[i]=0, если вершина i пока не проверена),
cnum – текущий номер в порядке обхода.
Трудоемкость алгоритма DFS на матрице смежности составляет O(|𝑽|^𝟐).
*/

    void deep(int cver, int* R, int& cnum)
    {
        R[cver] = ++cnum;
        for (int i = 0; i < vernum; i++)
            if (matrix[cver][i] && !R[i]) deep(i, R, cnum);

    }
    friend ostream& operator<<(ostream& out, MGraph& graph)
    {
        for (int i = 0; i < graph.getvernum(); i++)
        {
            out << endl;
            for (int j = 0; j < graph.getvernum(); i++)
            {
                out << graph.getmatrix(i, j) << " ";
            }
        }
        return out;
    }
    //поиск в ширину
    int* BFS(int start)
    {
        int u, x, * lev = new int[vernum];
        vector <int> QUE;
        for (u = 0; u < vernum; u++)
            lev[u] = 0;
        lev[start] = 1;
        QUE.insert(QUE.begin(), start);
        while (!QUE.empty())
        {
            u = QUE.back();
            for (x = 0; x < vernum; x++)
                if (matrix[u][x] && !lev[x])
                {
                    lev[x] = lev[u] + 1;
                    QUE.insert(QUE.begin(), x);
                }
            QUE.pop_back();

        }
        return lev;
    }
    //поиск в глубину
    int* DFS()
    {
        int i, cnum, * R = new int[vernum];
        for (i = 0; i < vernum; i++) R[i] = 0;
        for (cnum = i = 0; i < vernum; i++)
            if (!R[i])
                deep(i, R, cnum);
        return R;
    }
    void file(const char* name, int nver)
    {
        bool ver;
        ifstream fin(name);
        for (int i = 0; i < nver; i++)
        {
            for (int j = 0; j < nver; j++)
            {
                fin >> ver;
                if (ver)
                    this->setedge(i, j);
            }
        }
    }
    //формирование начальной раскраски, первый вызов рекурсивной функции Paint
    void init_paint()
    {
        zmin = vernum; //число различных цветов в Pmin
        Pmin = new int[vernum];
        Pcur = new int[vernum];
        for (int i = 0; i < vernum; i++)
            Pmin[i] = i;
        Pcur[0] = 0;
        Paint(0, 1);
    }
//gjkextybt vbybvfkmyjq hfccrhfcrb
    int* get_chrom()
    {
        return Pmin;
    }
    //рекурсивная функция раскраски
    void Paint(int k, int z)
    {
        int j;
        zmax = min(z + 1, zmin - 1); //максимальное число цветов
        for (int col = 0; col <= zmax; col++) //по цветам
        {
            for (j = 0; j <= k; j++) //проверка смежных
                if (matrix[j][k + 1] == 1 && Pcur[j] == col) break;
            if (j > k) //красим k+1 в цвет col
            {
                Pcur[k + 1] = col; zcur = max(col, z);
                if (k + 1 < vernum) Paint(k + 1, zcur);
                else if (zcur < zmin) //минимальная раскраска
                    for (zmin = zcur, j = 0; j <= vernum; j++)
                        Pmin[j] = Pcur[j];
            }
        }

    }
};
int main()
{
    setlocale(LC_ALL, "rus");
    MGraph test(6, 0);
    test.file("ver_6.txt", 6);
    int* BFS = test.BFS(0);
    int* components = test.getcomp();
    test.init_paint();
    int* chrom = test.get_chrom();
    int* DFS = test.DFS();
    cout << endl << "Поиск в ширину:" << endl;
    for (int i = 0; i < 6; i++)cout << BFS[i] << ' ';
    cout << endl << "Компоненты:" << endl;
    for (int i = 0; i < 6; i++)cout << components[i] << ' ';
    cout << endl << "Раскраска:" << endl;
    for (int i = 0; i < 6; i++)cout << chrom[i] << ' ';
    cout << endl << "Поиск в глубину:" << endl;
    for (int i = 0; i < 6; i++)cout << DFS[i] << ' ';
    cout << endl;


    MGraph test1(10, 0);
    test1.file("ver_12.txt", 10);
    int* BFS1 = test1.BFS(6);
    int* components1 = test1.getcomp();
    test1.init_paint();
    int* chrom1 = test1.get_chrom();
    int* DFS1 = test1.DFS();
    cout << endl << "Поиск в ширину:" << endl;
    for (int i = 0; i < 10; i++)cout << BFS1[i] << ' ';
    cout << endl << "Компоненты:" << endl;
    for (int i = 0; i < 10; i++)cout << components1[i] << ' ';
    cout << endl << "Раскраска:" << endl;
    for (int i = 0; i < 10; i++)cout << chrom1[i] << ' ';
    cout << endl << "Поиск в глубину:" << endl;
    for (int i = 0; i < 10; i++)cout << DFS1[i] << ' ';
    cout << endl;
}