====== Kruskalov algoritam i kod ======

**Kruskalov algoritam** je još jedan od algoritama koji određuju stablo minimalne dužine. \\
Algoritam:
  - Iz grafa G ukloniti sve grane.
  - Sortirati sve grane grafa G u nepoadajući niz prema njihovim dužinama.
  - Dodavati grane inicijalnom grafu po sortiranom redosledu tako da se ne stvore konture.
  - Ponavljati korak 3 n-1 puta.

//Primer: Formirati minimalno razapinjuće stablo koristeći Kruskalov algoritam.// \\

{{http://www.dodaj.rs/f/3R/yg/4juxLQ01/10.png}} \\

//Rešenje:// Popisaćemo sve grane iz grafa, sortirati u nepodajući niz . 
^grane	 ^težina	^soritrane grane	^tezina ^
|(a.b)	| 8	        |(eh)	                | 1 |
|(a,c)	| 11            |(c,e)	                | 2 |
|(b,c)	| 3     	|(f,h)	                | 2 |
|(b,d)	| 3	        |(b,c)	                | 3 |
|(c,e)	| 2	        |(b,d)                  | 3 |
|(c,f)	| 6	        |(h,i)	                | 3 |
|(d,g)	| 5	        |(d,e)              	| 4 |
|(e,h)	| 1	        |(d,g)              	| 5 |
|(f,h)	| 2	        |(c,f)              	| 6 |
|(h,i)	| 3	        |(g,h)              	| 6 |
|(g,i)	| 7	        |(g,i)              	| 7 |
|(g,h)	| 6	        |(a.b)              	| 8 |
|(d,e)	| 4	        |(a,c)              	| 11 |


Iz soritranog niza nećemo koristiti grane koje će stvoriti konture, a to su grane: (a,c), (d,e), (g,h), (g,i), (c,f).

{{http://www.dodaj.rs/f/2k/FU/3nJCL2Qe/ee.png?400x220}}

====== KOD ======
<code>
#include<stdio.h>
#include<stdlib.h>
#define MAX 100

typedef struct pgrana
{
	int pocetak;
	int kraj;
	double tezina;
} grana;

void Ulaz();
void Sort();

int dimenzija,brojGrana;
int boje[MAX];
grana graf[MAX],stablo[MAX];

int main(int argc,char* argv[])
{
	int i,j,uvrscene=0;
	
	Ulaz();
	Sort();
	
	for(i=0;i<dimenzija;i++)
		boje[i]=i;
	
	for(i=0;i<brojGrana;i++)
		if(boje[graf[i].pocetak] != boje[graf[i].kraj])
		{
			int stara=boje[graf[i].pocetak];
			for(j=0;j<dimenzija;j++)
				if(boje[j]==stara) boje[j]=boje[graf[i].kraj];
		
			for(j=0;j<dimenzija;j++)
				printf(" %d",boje[j]);
			
			printf("\n");
			
			stablo[uvrscene].pocetak=graf[i].pocetak;
			stablo[uvrscene].kraj=graf[i].kraj;
			stablo[uvrscene].tezina=graf[i].tezina;
			uvrscene++;
		}
	
	for(i=0;i<uvrscene;i++)
		printf("\n(%d %d %lf)",stablo[i].pocetak,stablo[i].kraj,stablo[i].tezina);
	
	return 0;
}

void Ulaz()
{
	int i,j,t;
	double tezina;
	scanf("%d %d",&dimenzija,&brojGrana);
	for(t=0;t<brojGrana;t++)
		scanf("%d%d%lf",&graf[t].pocetak,&graf[t].kraj,&graf[t].tezina);
	return;
}

void Sort()
{
	int i,j,ip;
	double dp;
	for(i=0;i<brojGrana-1;i++)
		for(j=i+1;j<brojGrana;j++)
			if(graf[i].tezina > graf[j].tezina)
			{
				ip = graf[i].pocetak;
				graf[i].pocetak=graf[j].pocetak;
				graf[j].pocetak=ip;
				
				ip = graf[i].kraj;
				graf[i].kraj=graf[j].kraj;
				graf[j].kraj=ip;
				
				dp = graf[i].tezina;
				graf[i].tezina=graf[j].tezina;
				graf[j].tezina=dp;
			}
	return;
}

</code>

[[ kruskalov algoritam |{{http://www.kikel.hr/images/strelica_l.gif}}]]