#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
#include <string.h>
#define MAX 30


typedef struct kante
{
    char knotenA[15];
    char knotenB[15];
    int pos_A;
    int pos_B;
    int cost;
}KANTE;

typedef struct KLIST
{
    KANTE data[MAX]; //Liste mit den eingegebenen Kanten
    int n;           //Länge der Liste
}KLIST;

KLIST klist;         //Kantenliste

int matrix[MAX][MAX],anzahl;
KLIST spanlist;      //Spannbaum Liste
void kruskal();
int find(int parent[],int position);
void union1(int parent[],int c1,int c2);
void sort();
void print();
char knoten[15][MAX]; //Namensspeicher Knoten
int tree; //
int main()
{
    //int anzahl;



    printf("Kruskal Algorithmus\n\n");
    int repeat = 1;
    //Auswahl maximaler oder minimaler Spannbaum
    while(repeat == 1){
        printf("Wollen Sie einen maximalen oder minimalen Spannbaum verwenden?\n");
        printf("Eingabe: 1 -> maximaler Spannbaum\n");
        printf("Eingabe: 2 -> minimaler Spannbaum\n");
        scanf("%d",&tree);

        if(tree == 1 || tree == 2)
        {
            repeat = 0;
        }
        else
        {
            printf("Eingabe nicht erkannt!\n");
            fflush(stdin);
        }

    }
    repeat = 1;
    //Einlesen der Knotennamen
    while(repeat == 1){
        printf("Bitte geben Sie die Anzahl der Knoten ein (maximal 30)\n");
        scanf("%d",&anzahl);
        if(anzahl < MAX && anzahl > 0)
        {
            repeat = 0;
        }
        else
        {
            printf("Eingabe nicht akzeptiert\n");
        }
        fflush(stdin);

    }

    for(int i = 0;i<anzahl;i++)
    {
        printf("\nKnoten %d\n",i);
        printf("**********\n");
        printf("Geben Sie einen Namen ein(15 Zeichen): ");
        scanf("%s",&knoten[i]);
    }


    //Einlesen der Kanten
    //int matrix[anzahl][anzahl];

    int count_kanten = 0;//Zählt Anzahl der Eingebenen Kanten

    //Durchlauf der Matrix und Speicherung der Wegkosten
    for(int i = 0;i<anzahl;i++)
    {
        for(int j = 0;j<anzahl;j++)
        {
            if(j > i){
                repeat = 1;
                while(repeat == 1)
                {
                    printf("\nWenn keine Kante/Verbindung -> 0 eingeben\n");
                    printf("Bitte Abstand/Kosten eingeben fuer:  %s nach %s\n",knoten[i],knoten[j]);
                    scanf("%d",&matrix[i][j]);
                    if(matrix[i][j] < 32000 && matrix[i][j] > -32000  )
                    {
                        repeat = 0;
                    }
                    else
                    {
                        printf("Eingabe nicht akzeptiert\n");
                    }
                    fflush(stdin);
                }
                if(matrix[i][j] != 0)
                {
                    count_kanten = count_kanten + 1;
                }
            }
            //Wenn Knoten auf sich selbst zeigt kosten = 0
            if(j == i)
            {
                matrix[i][j] = 0;
            }

        }

    }

    //Speicherung der Kanten in der Struktur Kanten mit Namen/Position/Wegkosten
    KANTE kanten[count_kanten];
    int k = 0;

    for(int i = 0;i< anzahl;i++)
    {
        for(int j = 0; j < anzahl;j++)
        {
            if(i < j && matrix[i][j] != 0)
            {
                    strcpy(kanten[k].knotenA,knoten[i]);
                    strcpy(kanten[k].knotenB,knoten[j]);
                    kanten[k].pos_A = i;
                    kanten[k].pos_B = j;
                    kanten[k].cost = matrix[i][j];
                    k = k + 1;
            }
        }
    }


    //Kopieren der eingebenen Werte in die hälfte unter der Diagonale in der Matrix
    for(int i = 0;i<anzahl;i++)
    {
        for(int j = 0;j<anzahl;j++)
        {
            if(j < i)
            {
                matrix[i][j] = matrix[j][i];
            }

        }

    }
    printf("\n");
   //Bubblesort :) Sortieren nach gewicht
   for (int i = 1; i < count_kanten ; i++)
   {
      for (int j = 0; j < count_kanten - i ; j++)
      {
          if (kanten[j].cost > kanten[j+1].cost)
          {
              KANTE temp = kanten[j];
              kanten[j] = kanten[j+1];
              kanten[j+1] = temp;
          }
      }
   }


//Ausgabe der Matrix
printf("\n");
printf("              ");
//Ausgabe der Knotennamen überhalb der Matrix
for(int i = 0;i<anzahl;i++)
{
    printf("%16s",knoten[i]);
}
printf("\n");

for(int i = 0;i<anzahl;i++)
{

        printf("%15s",knoten[i]);//Ausgabe der Namen am Zeilanfang
        for(int j = 0;j<anzahl;j++)
        {

            printf("%15d ",matrix[i][j]);//Ausgabe der Matrix

        }
        printf("\n");
    }



//Tabelle mit nach kosten sortierten Kanten
printf("\nKanten:");
printf("\nRANG             VON            NACH    GEWICHT     SPALTE      ZEILE\n");
for(int i = 0; i < k;i++)
{
    printf("%4d %15s %15s %10d %10d %10d\n",i,kanten[i].knotenA,kanten[i].knotenB,kanten[i].cost,kanten[i].pos_A,kanten[i].pos_B);
}

printf("\n");

//Aufruf Kruskal Algorithmus
kruskal();
//Ausgabe der Ergebnisse
print();
}
//Funktionen
void kruskal()
{
    int parent[MAX],i,j,cno1,cno2;
    klist.n=0;

    for(i=1;i<anzahl;i++)
        for(j=0;j<i;j++)
        {
            if(matrix[i][j]!=0)
            {
                //Speicher der Position und Kosten der Kanten in einer Liste. n zählt die Länge der Liste
                klist.data[klist.n].pos_A=i;
                klist.data[klist.n].pos_B=j;
                klist.data[klist.n].cost=matrix[i][j];
                klist.n++;
            }
        }
    //Sortiert die Liste mit Kanten
    sort();
    //Befüllt Parent Array
    for(i=0;i<anzahl;i++)
    {
        parent[i]=i;
    }

    spanlist.n=0;

    for(i=0;i<klist.n;i++)
    {

        //Überprüft ob beide Kanten den gleichen Parent haben
        cno1=find(parent,klist.data[i].pos_A);
        cno2=find(parent,klist.data[i].pos_B);
        //Wenn nicht gleicher Parent werden werte aus der kanten liste in der Spannbaumliste gespeichert
        if(cno1!=cno2)
        {
            spanlist.data[spanlist.n]=klist.data[i];
            spanlist.n=spanlist.n+1;//index in der Spannbaumliste
            union1(parent,cno1,cno2);
        }
    }
}

int find(int parent[],int position)
{
    return(parent[position]);//Such Wert im Array Parent an der übergebenen Position
}

//Weist beiden Knoten den gleichen Parent zu
void union1(int parent[],int c1,int c2)
{
    for(int i=0;i<anzahl;i++)
    {
        if(parent[i]==c2)
        {
            parent[i]=c1;
        }
    }
}

void sort()
{
    int i,j;
    KANTE temp;
    //Für max Spannbaum
    //Kosten der Kanten weerden negiert
    if(tree == 1)
    {

        for(int i = 0;i < klist.n;i++)
        {
            klist.data[i].cost = (klist.data[i].cost * (-1));
        }
    }
    //Elemente in der kantenliste werden nach kosten sortiert
    for(i=1;i<klist.n;i++)
        for(j=0;j<klist.n-1;j++)
            if(klist.data[j].cost>klist.data[j+1].cost)
            {
                temp=klist.data[j];
                klist.data[j]=klist.data[j+1];
                klist.data[j+1]=temp;
            }
    //Für max Spannbaum
    // Kosten der Kanten werden wieder negiert
    if(tree == 1)
    {
        for(int i = 0;i < klist.n;i++)
        {
            klist.data[i].cost = (klist.data[i].cost * (-1));
        }
    }
}
//Ausgabe der Ergebnisse
void print()
{
    int i,cost=0;

    for(i=0;i<spanlist.n;i++)
    {

        printf("\nKante: %s <--> %s kosten:%d",knoten[spanlist.data[i].pos_B],knoten[spanlist.data[i].pos_A],spanlist.data[i].cost);
        cost=cost+spanlist.data[i].cost;
    }

    printf("\n\nKosten des Spannbaums = %d",cost);
}