#include <stdio.h>
#include <stdlib.h>

struct kante {
	char knoten1;
	char knoten2;
	int wert;
	int genommen;
};

struct kante kanten [] =
{
	{'a','b',4,0},
	{'a','h',8,0},
	{'b','h',11,0},
	{'b','c',8,0},
	{'h','i',7,0},
	{'h','g',1,0},
	{'i','g',6,0},
	{'i','c',2,0},
	{'c','f',4,0},
	{'c','d',7,0},
	{'g','f',2,0},
	{'d','f',14,0},
	{'e','d',9,0},
	{'e','f',10,0}
};

#define KANTEN (sizeof(kanten)/sizeof(struct kante))

int father [KANTEN];

int ergebnis [KANTEN];

void makeset (int kante)
{
	father [kante] = kante;
}

int findset (int kante)
{
	while (father [kante] != kante)
		kante = father [kante];
	return kante;
}

void unionset (int u, int v)
{
	father [u] = v;
}

void nimm (struct kante k)
{
	int i;

	// Markiere den tatsächlichen Knoten in der Menge
	for (i=0; i<KANTEN;i++)
	{
		// Suche die Kante k
		if (	kanten[i].wert == k.wert &&
			kanten[i].knoten1 == k.knoten1 &&
			kanten[i].knoten2 == k.knoten2)
		{
			kanten[i].genommen = 1;
		}
	}

	printf ("Nimm Kante (%c,%c) auf.\n",k.knoten1,k.knoten2);
}

int compar (const void * i1, const void * i2)
{
	struct kante * k1 = (struct kante*) i1;
	struct kante * k2 = (struct kante*) i2;

	if (k1->wert > k2->wert) return 1;
	else if (k1->wert < k2->wert) return -1;
	else return 0;
}

void kruskal ()
{
	struct kante k;
	int i;
	qsort (kanten, KANTEN, sizeof (struct kante), compar);
	
	for (i=0; i<KANTEN;i++)
	{
		makeset (i);
	}

	for (i=0; i<KANTEN; i++)
	{
		k= kanten [i];

		if (findset(k.knoten1-'a') != findset(k.knoten2-'a'))
		{
			unionset (findset (k.knoten1-'a'), findset (k.knoten2-'a'));
			nimm (k);
		}
	}
}

struct kante genommen [KANTEN];
struct kante auswahl [KANTEN];


/**Sehr inneffizient und auch falsch, da die Kreisschlussbedingung nicht
 * ganz hinhaut. Könnte man effizient erledigen mithilfe eines Heaps.*/
void prim ()
{
	struct kante k;
	int i,j,t;
	int anz_auswahl;
	int dont_take;

	// finde kleinste Kante
	// (könnte auch mit beliebigen Knoten anfangen)
	k=kanten[0];
	for (i=0; i< KANTEN; i++)
	{
		if (kanten[i].wert < k.wert) 
		{
			k=kanten[i];
		}
	}
		
	nimm (k);
	for (i=1; i< KANTEN; i++)
	{		
		// Auswahl initialisieren
		anz_auswahl = 0;
		for (j=0; j<KANTEN; j++)
		{
			auswahl[j].knoten1=0;
			auswahl[j].knoten2=0;
			auswahl[j].wert=0;
		}

		//welche Kanten kommen in Frage?
		for (j=0; j<KANTEN; j++)
		{
			if (! kanten[j].genommen)
				k= kanten[j];

			for (t=0; t<KANTEN; t++)
			{
			// *eine* Kante angrenzend?
			if (	// entweder knoten1 (aber nicht 2) hat Verbindung
				((kanten[j].knoten1 == k.knoten1 ||
				kanten[j].knoten2 == k.knoten1) &&
				! (kanten[j].knoten1 == k.knoten2 ||
				kanten[j].knoten2 == k.knoten2)) ||

				// oder knoten2 (aber nicht 1)!
				(! (kanten[j].knoten1 == k.knoten1 ||
				kanten[j].knoten2 == k.knoten1) &&
				(kanten[j].knoten1 == k.knoten2 ||
				kanten[j].knoten2 == k.knoten2)))

				// Ziehe k in Betracht
				auswahl[anz_auswahl++] = k;
			}
		}
		
		if (auswahl[0].knoten1 == 0)
			return;	// keine Auswahl mehr vorhanden!
		// Minimale Kante aus Auswahl bestimmen?
		k=auswahl[0];
		for (j=0; j<anz_auswahl; j++)
		{
			if (auswahl[j].wert < k.wert)
				k = auswahl[j];
		}
		genommen [i] = k;
		nimm (k);
	}
}

int main()
{
	prim ();
	return 0;
}