Monique

#include <stdio.h>
#include <iostream>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include <ctime>

using namespace std;

class Krawedz
{
    public:
        int stad;
        int dokad;
        int waga;
};

void sortowanie(Krawedz **K1, int k)
{
    Krawedz pomocnik;

    for (int i=1; i<= k-1; i++)
        for (int j=1; j<= k-i; j++)
            if ( (*K1)[j].waga > (*K1)[j+1].waga )
            {
                pomocnik    = (*K1)[j];
                (*K1)[j]   = (*K1)[j+1];
                (*K1)[j+1] = pomocnik;
            }
}


int kruskal(int n, Krawedz **K1, Krawedz **K2 )
{
    int *A = (int*)malloc(sizeof(int) * (n + 3));
    int  j, k, u, v, w;
    int suma = 0;

    for (int i=1; i<=n; i++) A[i] = 0;

    k = 1;
    j = 1;
    while (k < n)
    {
        u = (*K1)[j].stad;
        v = (*K1)[j].dokad;
        j++;
        if ( A[u] == 0 || A[v] == 0 || A[u] != A[v] )
        {
            suma++;
            (*K2)[suma] = (*K1)[j - 1];
            if ( A[u] == 0 && A[v] != 0 )
            {
                w = u;
                u = v;
                v = w;
            }
            if (A[u] == 0) A[u] = u;

            if (A[v] == 0) A[v] = A[u];
            else
            {
                w = A[v];
                for (int i = 1; i <= n; i++)
                    if (A[i] == w ) A[i] = A[u];
            }
            k++;
        }
    }

    delete A;
    return suma;
}


int main()
{
    int n, k, suma, p, a = 0, y, x;

    srand((unsigned)time(NULL));

    cout << endl << endl << endl;
    cout << "\t\E[34m..:: MODELOWANIE GRAFOW - ALGORYTMY KRUSKALA I PRIMA ::..\E[30m" << endl;
    cout << "\t\tMonika Kosinska, 165060" << endl << endl;
    cout << "\t\tPodaj liczbe wierzcholkow: ";
    cin >> n;
    cout << endl;
    cout << "\t\tPodaj procentowa (%) ilosc krawedzi: ";
    cin >> k;
    cout << endl << endl;

    p = n * (n - 1) / 2 * k / 100;

    Krawedz *K1 = (Krawedz*)malloc((p + 3)* sizeof(Krawedz));
    Krawedz *K2 = (Krawedz*)malloc((p + 3)* sizeof(Krawedz));

    for (int i = 1; i <= n - 1; i++)
    {
        K1[i].stad = i;
        K1[i].dokad = i + 1;
        K1[i].waga = 1 + rand() % 10;
    }
    for (int i = n; i <= p;)
    {
        int q=0;
        y = 1 + rand() % (n);
        x = 1 + rand() % (n);
        if (x != y)
        {
            for (int j = 1; j <= p; j++)
            {
                //cout << "\t\t\t" << K1[j].stad << " stad " << K1[j].dokad << endl;
                //cout << "\t\t\t" << x << " <-x " << y << " <-y " << endl;
                if (K1[j].stad == x)
                    if (K1[j].dokad == y)
                    {
                        q = 1;
                    }
                if (K1[j].stad == y)
                    if (K1[j].dokad == x)
                    {
                        q = 1;
                    }
            }

            if (q == 0)
            {
                K1[i].stad = x;
                K1[i].dokad = y;
                K1[i + 1].stad = y; // gdy skierowany//
                K1[i + 1].dokad = x;//
                K1[i].waga = 1 + rand() % 9;
                K1[i + 1].waga = K1[i].waga;//
                i++;
            }
        }
    }

    cout << endl << endl << "\t\t\t \E[30mMOJ WYGENEROWANY GRAF: " << endl << endl;

    for(int i = 1; i <= p; i++)
        cout << "\t\t\t" << K1[i].stad << "\E[32m -> \E[30m" << K1[i].dokad << "\E[32m : \E[36m" << K1[i].waga << "\E[30m" << endl;

    //trzeba policzyc czas trwania Kruskala******************************

    clock_t StartTime, StopTime; //potrzebne dane do liczenia czasu trwania - bibloteka ctime

    StartTime = clock(); //uruchamiam zegar

    sortowanie(&K1, p);

    suma = kruskal(n, &K1, &K2 );

    StopTime = clock(); //zatrzymuje zegar

    double czas = 0;

    czas = (StopTime - StartTime) / 1000.0 ; //licze czas

    //*********************************************************************

    int pom = 0;

    cout << endl << endl << "\t\t\t \E[30mNAJKROTSZA DROGA W TYM GRAFIE TO: " << endl << endl;

    for (int i = 1; i <= suma; i++)
    {
        cout << "\t\t\t\E[33m" << K2[i].stad << " \E[32m-> \E[33m" << K2[i].dokad << "\E[32m :\E[34m " << K2[i].waga<<endl;
        pom += K2[i].waga;
    }
    cout << endl << endl << "\t\t\t\t" << "\E[30m Wartość MST:\E[31m " << pom << "\E[30m" << endl;
    cout << endl << endl << "\t\t\t\t" << "\E[30m Czas trwania Kruskala:\E[31m " << czas << "\E[30m" << endl << endl << "\t\t\t\t";
    delete K1;
    delete K2;
    return 0;
}