Kolowium grafy (90% + po tym dostałem 5.0 na koniec )

#include<iostream>
#include<fstream>


using namespace std;

///@attention Kolokwium znajduje się na dole pracy

struct Graf_MacierzSasiedztwa // macierz sąsiedztwa
{
    double** matrix; //macierz
    int size;    // rozmiar
};

struct Node
        {
    Node* next;
    int from;
    int to;
    double val;
        };

void show_list_rek(Node * H) {
    if (H != nullptr) {
        cout << "Wartosc "<< H -> val << " ->";
        if (H -> next != nullptr)
            show_list_rek(H -> next);
        else cout << "nullptr";
    }
}
void add(Node * & H,int to, double value) {
    Node * p = new Node;
    p -> val = value;
    p->to=to;
    p -> next = H;
    H = p;

}

void add(Node * & H,int to ,int from, double value) {
    Node * p = new Node;
    p -> val = value;
    p->to=to;
    p -> next = H;
    p->from=from;
    H = p;

}

void add(Node * & H,Node* p) {
    Node *k= new Node(*p);

    k -> next = H;

    H = k;

}
void swapValue( Node *a, Node *b)
{
    int temp = a->val;
    a->val = b->val;
    b->val = temp;
}


void bubbleSort(Node *&head)
{
    int i;
    bool isSwapNessesary;
    struct Node *p;
    struct Node *lastStand = nullptr;
    if (head == nullptr)
        return;
    do
    {
        isSwapNessesary = false;
        p = head;

        while (p->next != lastStand)
        {
            if (p->val > p->next->val)
            {
                swapValue(p, p->next);
                isSwapNessesary = true;
            }
            p = p->next;
        }
        lastStand = p;
    }
    while (isSwapNessesary);
}

int calculateNumberOfElementsInLinkedList(Node *&head) {
    int licznik = 0;
    Node * p = head;
    while (p) // liczę ilość elementów w tablicy
    {
        licznik++;
        p = p -> next;

    }
    return licznik;
}

Node *jumpOverGapRange(int gap, int iterator, Node *tmpHead, Node *endingElement) {
    endingElement = tmpHead;
    iterator = 1;
    while (endingElement->next && iterator < gap) {
        endingElement = endingElement->next;
        iterator++;
    }
    return endingElement;
}
void sortowanieGrzebieniowe(Node*& head) {

    if (head) {
        if (head -> next == nullptr) ///jednoelementowa tablica
        {
            return;
        }
        else
        {
            int gap = calculateNumberOfElementsInLinkedList(head);
            int iterator = 0;
            bool replace = true;
            Node* before = nullptr;
            Node* tmp = nullptr;
            Node* tmpHead;
            Node* endingElement;
            Node* afterEndingElement = nullptr;

            while (gap > 1 || replace)
            {
                gap = gap * 10 / 13;
                if(gap==0)
                {
                    gap=1;
                }
                endingElement =head;
                tmpHead = head;
                replace = false;
                if (gap == 1) {
                    bubbleSort(head);
                    continue;
                }
                while (tmpHead && endingElement->next->next) {

                    endingElement = jumpOverGapRange(gap, iterator, tmpHead, endingElement);

                    if (tmpHead->val > endingElement->next->val) {
                        if (before == nullptr)
                        {
                            tmp = endingElement->next;
                            afterEndingElement = tmp->next;
                            tmp->next = tmpHead->next;
                            endingElement->next = tmpHead;
                            tmpHead->next = afterEndingElement;

                            tmpHead = tmp;
                            head = tmp;
                        }
                        else
                        {
                            tmp = endingElement->next;
                            afterEndingElement = tmp->next;
                            tmp->next = tmpHead->next;
                            endingElement->next = tmpHead;
                            before->next = tmp;
                            tmpHead->next = afterEndingElement;

                            tmpHead = tmp;
                        }
                    }
                    before = tmpHead;
                    tmpHead = tmpHead->next;
                }
            }
        }}}

Node* sortedMerge(Node* a, Node* b)
{
    Node* result = nullptr;


    if (a == nullptr)
        return(b);
    else if (b == nullptr)
        return(a);

    if (a->val <= b->val)
    {
        result = a;
        result->next = sortedMerge(a->next, b);
    }
    else
    {
        result = b;
        result->next = sortedMerge(a, b->next);
    }
    return(result);
}

Node* sortedMerge(Node* a, Node* b,int from)
{
    Node* result = nullptr;


    if (a == nullptr)
        return(b);
    else if (b == nullptr)
        return(a);

    if (a->val <= b->val)
    {
        result = a;
        result->from=from;
        result->next = sortedMerge(a->next, b,from);
    }
    else
    {
        result = b;
        result->from=from;
        result->next = sortedMerge(a, b->next,from);
    }
    return(result);
}
void przepnijWskaznikHeda(Node *&scalona,Node *&wynikowa)
{
    Node * pom=scalona;
    scalona=scalona->next;
    pom->next=wynikowa;
    wynikowa=pom;
}
///
/// \param scalona
/// \param wynikowa
void przepnijWskaznikNastepnika(Node *&scalona,Node *&wynikowa)
{
    Node * pom=scalona;
    scalona=scalona->next;
    pom->next=wynikowa->next;
    wynikowa->next=pom;
}
/// @warning NIE DZIALA POPRAWNIE DLA SCIEZEK WZGLEDNYCH
/// \param FileName  jako parametr podac sciezke bezwzgledna
/// \return zwraca macierz sasiedzctwa

Graf_MacierzSasiedztwa* CzytajGraf(string FileName)
{
    Graf_MacierzSasiedztwa* gr = new Graf_MacierzSasiedztwa;
    fstream czytaj ;
    int value = 0;
    czytaj.open(FileName);
    czytaj >> gr->size;
    gr->matrix = new double* [gr->size];
    for (int i = 0; i < gr->size; i++)
    {
        gr->matrix[i] = new double[gr->size];
    }
    for (int i = 0; i < gr->size; i++)
    {
        for (int j = 0; j < gr->size; j++)
        {
            gr->matrix[i][j] = 0;
        }
    }

    for (int i = 0; i < gr->size; i++)
    {
        for (int j = 0; j < gr->size; j++)
        {
            czytaj >> gr->matrix[i][j];
        }
    }
    czytaj.close();
    return gr;
}

///@attention Wypisywanie grafu na bazie macierzy sasiedzctwa
/// \param gr
void WypiszGraf(Graf_MacierzSasiedztwa* gr)
{
    for (int i = 0; i < gr->size; i++)
    {
        for (int j = 0; j < gr->size; j++)
        {
            cout << gr->matrix[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl << endl;
}

///@attention Lista sasiedzctwa nie pamieta skad dane byly brane wiec warto zapamietac te dane przeksztalcajac liste sasiedzctwa lub wyciagajac dane
/// \param matrix
/// \param size
/// \return listę sąsiedzctwa

Node **listaSasiedztwa(double **matrix,int size)
{
    Node** LN = new Node* [size];
    for (int i = 0; i < size ; i++)
        LN[i] = nullptr;
    for (int i = 0; i < size; i++)
        for (int j = 0; j < size; j++)
            if(matrix[i][j]!=0)
                add(LN[i], j, matrix[i][j]);

    return LN;

}

void deleteFirst(Node * & H) {
    if (H != nullptr) {
        Node * p = H;
        H = H -> next;
        delete p;
    }
}


void wypiszLas(int size, const int *tablicaLasow) {
    for (int i = 0; i < size; i++)
    {
        cout << tablicaLasow[i];
    }
    cout<<endl;
}
///@warning KRUSKAL moze być Zaimplementowany NIEPOPRAWNIE ze względu na złe dane wejściowe !
///@DEPRECATED Nie warto uzywac
///@param listaSasiedzctwa
///NIEPOPRAWNA IMPLEMENTACJA ALGORYTMU KRUSKALA ZE WZGLĘDU NA DANE Z LISTY SĄSIEDZCTWA
///@param size
///rozmiar tablicy
Node * algorytm_Kruskala(Node ** listaSasiedzctwa, int size)
{
    int * tablicaKolorow= new int [size];
    int * tablicaLasow=new int [size];

    Node *wynikowa= nullptr;


    add(wynikowa,0,0);
    Node *scalona= nullptr;
    for(int i=0;i<size;i++)
    {
        bubbleSort(listaSasiedzctwa[i]);
        scalona= sortedMerge(scalona,listaSasiedzctwa[i],i);
        tablicaLasow[i]=0;
        tablicaKolorow[i]=0;
    }
    int licznikLasow=1;
    while(scalona!= nullptr)
    {
        if((tablicaKolorow[scalona->from]==0)&&tablicaKolorow[scalona->to]==0)
        {
            tablicaKolorow[scalona->from]=1;
            tablicaKolorow[scalona->to]=1;
            tablicaLasow[scalona->to]=licznikLasow;
            tablicaLasow[scalona->from]=licznikLasow;
            licznikLasow++;
            przepnijWskaznikHeda(scalona,wynikowa);
            wypiszLas(size, tablicaLasow);
//            add(wynikowa,scalona);
//            deleteFirst(scalona);

        }
        else if(tablicaKolorow[scalona->from]==0 || tablicaKolorow[scalona->to]==0)
        {
            if(tablicaKolorow[scalona->from]!=0)
            {
                tablicaKolorow[scalona->to]=1;
                tablicaLasow[scalona->to]= tablicaLasow[scalona->from];

                przepnijWskaznikHeda(scalona,wynikowa);
                wypiszLas(size, tablicaLasow);
            } else
            {
                tablicaKolorow[scalona->from]=1;
                tablicaLasow[scalona->from]=tablicaLasow[scalona->to];


                przepnijWskaznikHeda(scalona,wynikowa);
                wypiszLas(size, tablicaLasow);
            }
        } else if((tablicaKolorow[scalona->from]!=0 && tablicaKolorow[scalona->to]!=0)&& tablicaLasow[scalona->from]!= tablicaLasow[scalona->to])
        {
            int lasAktualnyDo=tablicaLasow[scalona->to];
            int lasAktualnyOd=tablicaLasow[scalona->from];

            for(int i=0;i<size;i++)
            {
                if(tablicaLasow[i]==lasAktualnyOd||tablicaLasow[i]==lasAktualnyDo)
                {
                    tablicaLasow[i]=licznikLasow;
                }
                wypiszLas(size, tablicaLasow);
            }
            licznikLasow++;
            przepnijWskaznikHeda(scalona,wynikowa);

        } else if((tablicaKolorow[scalona->from]!=0&& tablicaKolorow[scalona->to]!=0)&&(tablicaLasow[scalona->to]==tablicaLasow[scalona->from]))
        {
            cout<<"Usuwam krawedz : "<<scalona->from<<" -> "<<scalona->to<<" o wartosci "<<scalona->val<<endl;
            deleteFirst(scalona);
        }
    }
    deleteFirst(wynikowa);
    return wynikowa;
}
///@waring Może działać źle
/// \param scalona
/// Jest to lista krawedzi scalona
/// \param size
/// jest to rozmiar tablicy
/// \return
/// zwraca najkrótszą trase która wystarczy do przejscia grafu
Node * algorytm_Kruskala(Node * &scalona, int size)
{
    bubbleSort(scalona);
    int * tablicaKolorow= new int [size];
    int * tablicaLasow=new int [size];

    Node *wynikowa= nullptr;

    cout<<" KRUSKAL DEBUG  ZACZYNA OD LISTY"<<endl;
    show_list_rek(scalona);
    add(wynikowa,0,0);

    bubbleSort(scalona);
    for(int i=0;i<size;i++)
    {
        tablicaLasow[i]=0;
        tablicaKolorow[i]=0;
    }
    int licznikLasow=1;
    while(scalona!= nullptr)
    {
        if((tablicaKolorow[scalona->from]==0)&&tablicaKolorow[scalona->to]==0)
        {
            tablicaKolorow[scalona->from]=1;
            tablicaKolorow[scalona->to]=1;
            tablicaLasow[scalona->to]=licznikLasow;
            tablicaLasow[scalona->from]=licznikLasow;
            licznikLasow++;
            przepnijWskaznikHeda(scalona,wynikowa);
            wypiszLas(size, tablicaLasow);
//            add(wynikowa,scalona);
//            deleteFirst(scalona);

        }
        else if(tablicaKolorow[scalona->from]==0 || tablicaKolorow[scalona->to]==0)
        {
            if(tablicaKolorow[scalona->from]!=0)
            {
                tablicaKolorow[scalona->to]=1;
                tablicaLasow[scalona->to]= tablicaLasow[scalona->from];

                przepnijWskaznikHeda(scalona,wynikowa);
                wypiszLas(size, tablicaLasow);
            } else
            {
                tablicaKolorow[scalona->from]=1;
                tablicaLasow[scalona->from]=tablicaLasow[scalona->to];


                przepnijWskaznikHeda(scalona,wynikowa);
                wypiszLas(size, tablicaLasow);
            }
        } else if((tablicaKolorow[scalona->from]!=0 && tablicaKolorow[scalona->to]!=0)&& tablicaLasow[scalona->from]!= tablicaLasow[scalona->to])
        {
            int lasAktualnyDo=tablicaLasow[scalona->to];
            int lasAktualnyOd=tablicaLasow[scalona->from];

            for(int i=0;i<size;i++)
            {
                if((tablicaLasow[i]==lasAktualnyOd)||(tablicaLasow[i]==lasAktualnyDo))
                {
                    tablicaLasow[i]=licznikLasow;
                }
                wypiszLas(size, tablicaLasow);
            }
            licznikLasow++;
            przepnijWskaznikHeda(scalona,wynikowa);

        } else if((tablicaKolorow[scalona->from]!=0&& tablicaKolorow[scalona->to]!=0)&&(tablicaLasow[scalona->to]==tablicaLasow[scalona->from]))
        {
            cout<<"Usuwam krawedz : "<<scalona->from<<" -> "<<scalona->to<<" o wartosci "<<scalona->val<<endl;
            deleteFirst(scalona);
        }
    }
    cout<<"Kończy na Liscie "<<endl;
    show_list_rek(wynikowa);
    deleteFirst(wynikowa);
    return wynikowa;
}
///
/// \param macierzSasiedztwa
/// \return
Node * listaKrawedzi(Graf_MacierzSasiedztwa * macierzSasiedztwa)
{
    Node * h= nullptr;
    for (int i = 0; i < macierzSasiedztwa->size; i++)
        for (int j = 0; j < macierzSasiedztwa->size; j++)
            if(macierzSasiedztwa->matrix[i][j]!=0)
                add(h, j,i, macierzSasiedztwa->matrix[i][j]);

    return h;
}
///@attention działa w numerowaniu od Zera
/// \param listaKrawedzi
/// \param size
/// \return liste sasiedzctwa
Node ** listaSasiedzctwaNaBazieListyKrawedzi(Node *listaKrawedzi,int size) // działa w numerowaniu od Zera
{
    Node** LN = new Node* [size];
    for (int i = 0; i < size ; i++)
        LN[i] = nullptr;
    while(listaKrawedzi!= nullptr)
    {
        add(LN[listaKrawedzi->from],listaKrawedzi);
        deleteFirst(listaKrawedzi);

    }


    return LN;
}
///
/// \param kolory Tablica kolorow
/// \param size rozmiar tablicy
/// \return zwraca prawde dla tablicy kolorow majacej bialy wierzcholek
bool sprawdzCzyTablicaKolorowMaNieodwiedzonyWierzcholek(int * kolory,int size)
{
    for(int i=0;i<size;i++)
    {
        if(kolory[i]==0)
        {
            return true;
        }
    }
    return false;
}

void wypisywanieTECHNICZNE(int * kolory,int size)
{
    for(int i=0;i<size;i++)
    {
cout<<kolory[i]<<" ";
    }
    cout<<endl;
}


///@attention wierzcholki do starting point liczymy od 0 a size-1 jest to ostatni !
/// \param listaSasiedzctwa lista sasiedzctwa
/// \param size ilosc wierzcholkow
/// \param startingPoint wierzcholek w ktorym zaczynamy przechodzenie grafu
/// \return najkrotsza sciezka


Node * algorytmPrima(Node ** listaSasiedzctwa, int size , int startingPoint)
{
    Node * wynikowa= nullptr;
    int * tablicaKolorow=new int[size];
    for(int i=0;i<size;i++)
    {
        tablicaKolorow[i]=0;
    }
    for(int i=0;i<size;i++)
    {
       Node* p=listaSasiedzctwa[i];
       while(p!= nullptr)
       {
           p->from=i;
           p=p->next;
       }
    }

    tablicaKolorow[startingPoint]=1; // odwiedzamy pierwszy wierzchołek
    cout<<"Mam tablice kolorow oraz startowy punkt"<<startingPoint<<endl;
    while(sprawdzCzyTablicaKolorowMaNieodwiedzonyWierzcholek(tablicaKolorow,size))
    {
        double minimalnyPKT=DBL_MAX;
        Node * kandydat= nullptr;
        cout<<"Przejscie petli"<<endl;
        for(int i =0 ;i < size;i++)
        {

            if(tablicaKolorow[i]!=0)
            {
                Node * p = listaSasiedzctwa[i];

                while(p!= nullptr)
                {
                    cout<<"przechodze po liscie "<<i<<"I jestem w elemencie"<<p->val<<" wskazujacym na kolor"<<tablicaKolorow[p->to]<<endl;
                    if(p->val<minimalnyPKT&&tablicaKolorow[p->to]==0) // sprawdza poprawną drogę do nieodwiedzonego wierzchołka
                    {

                     kandydat=p;
                        minimalnyPKT=kandydat->val;
                        cout<<"NADPISANO ("<<p->val<<")"<<endl;
                    }
                    p=p->next;
                }

            }

        }

        wypisywanieTECHNICZNE(tablicaKolorow,size);
        tablicaKolorow[kandydat->to]=1;

        cout<<"Dodano krawedz o wielkosci "<<kandydat->val<<"<<<<<<<<<<<<<<<<<<<"<<endl;
        add(wynikowa,kandydat);
    }

    return wynikowa;
}



///@attention Lista unikalnych krawedzi moze być wykorzystywana do algorytmu kruskala
/// \param macierzSasiedztwa
/// \return

Node * stworzNaBazieMacierzySasiedzctwaListeUnikalnychKrawedzi( Graf_MacierzSasiedztwa *macierzSasiedztwa)
{
    Node * head= nullptr;
    for (int i = 0; i < macierzSasiedztwa->size; i++)
        for (int j = 0; j <  i; j++)
            if (macierzSasiedztwa->matrix[i][j] != 0)
                add(head,i, j, macierzSasiedztwa->matrix[i][j]);
    return head;
}

//////// KOLOKWIUM ////////////
//////Zadanie 1 /////////
void zadanie1(Node ** &listaSasiedzctwa,int rozmiar)
{
    int liczbaUsunetych=0;
    double srednia=0;
    double suma=0;
    int iloscElementow=0;
    for(int i=0;i<rozmiar;i++) ///zlicza sume elementow i liczbe elementow w liscie sasiedzctwa
    {
        Node * p= listaSasiedzctwa[i];

        while(p!= nullptr)
        {
            suma+=p->val;
            iloscElementow+=1;
            p=p->next;
        }
    }

    srednia=suma/iloscElementow;
    double wartoscKandydata=DBL_MAX;

    for(int i=0;i<rozmiar;i++)
    {
        Node * p=listaSasiedzctwa[i];

        while(p!= nullptr)
        {
            if(abs(srednia-wartoscKandydata)>p->val)/// warunek na bliskosc do sredniej
            {
                wartoscKandydata=p->val;
            }
            p=p->next;
        }
    }

    for (int i = 0; i < rozmiar; i++) {//usuwanie wszystkich
        Node *p= listaSasiedzctwa[i];
        if(wartoscKandydata==p->val)
        {
           Node * k=p;
           p=p->next;
           delete k;
        }
        while(p!= nullptr&&p->next)
        {
            if(p->next->val==wartoscKandydata)
            {
                Node *tymczasowa=p->next;
                p->next=p->next->next;
                delete tymczasowa;
                liczbaUsunetych++;
            }
            p=p->next;
        }
    }
    cout<<endl<<"Liczba usunietych krawedzi "<<liczbaUsunetych<<endl;
}
///////Zadanie 2////////

void zadanie2(Node** ListaSasiedztwa, int macierz[8][8], Node*& ListaKrawedzi, int rozmiar)
{
    for (int i = 0; i < rozmiar; i++)
    {

        while (ListaSasiedztwa[i] != nullptr)
        {
            if ((int) ListaSasiedztwa[i]->val % 2 == 0)
            {
                Node* tymczasowa1 = ListaKrawedzi;
                ListaKrawedzi = new Node;
                ListaKrawedzi->from = i;
                ListaKrawedzi->to = ListaSasiedztwa[i]->to;
                ListaKrawedzi->val = ListaSasiedztwa[i]->val;
                ListaKrawedzi->next = tymczasowa1;
                Node* tymczasowa2 = ListaSasiedztwa[i];
                ListaSasiedztwa[i] = ListaSasiedztwa[i]->next;
                delete tymczasowa2;
            }
            else
            {
                Node* tymczasowa = ListaSasiedztwa[i];
                macierz[i][tymczasowa->to] = tymczasowa->val;
                ListaSasiedztwa[i] = ListaSasiedztwa[i]->next;
                delete tymczasowa;
            }
        }
    }

}
int main()
{
    Graf_MacierzSasiedztwa* gr = CzytajGraf("D:\\Grafy\\graf.txt");
    WypiszGraf(gr);
  Node ** listaSasiedzctwa=  listaSasiedztwa(gr->matrix, gr->size);


   Node * lista1= algorytmPrima(listaSasiedzctwa, gr->size, 7);

cout<<"Wyszlo";
   gr = CzytajGraf("D:\\Grafy\\graf.txt");

    show_list_rek(lista1);
    cout<<endl;
    WypiszGraf(gr);
    Node * listaKrawedzi=stworzNaBazieMacierzySasiedzctwaListeUnikalnychKrawedzi(gr);
    listaSasiedzctwa=  listaSasiedztwa(gr->matrix, gr->size);
    cout<<endl<<endl;
    for(int i=0;i<gr->size;i++)
    {
        Node *p= listaSasiedzctwa[i];
        show_list_rek(p);
        cout<<endl;
    }
    zadanie1(listaSasiedzctwa,gr->size);
    cout<<endl;

     listaSasiedzctwa = listaSasiedztwa(gr->matrix, gr->size);
    int matrix[8][8];
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            matrix[i][j] = 0;

     listaKrawedzi = nullptr;
    zadanie2(listaSasiedzctwa, matrix, listaKrawedzi, 8);
    show_list_rek(listaKrawedzi);
    for (int i = 0; i < 8; i++)
    {
        cout << endl;
        for (int j = 0; j < 8; j++)
            cout << matrix[i][j] << " ";
    }
    return 0;
}