This is an old revision of the document!


Kruskalov algoritam i kod

Kruskalov algoritam je još jedan od algoritama koji određuju stablo minimalne dužine.
Algoritam:

  1. Iz grafa G ukloniti sve grane.
  2. Sortirati sve grane grafa G u nepoadajući niz prema njihovim dužinama.
  3. Dodavati grane inicijalnom grafu po sortiranom redosledu tako da se ne stvore konture.
  4. Ponavljati korak 3 n-1 puta.

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


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).

KOD

#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;
}

 
kruskalov_algoritam_i_kod.1356914253.txt.gz · Last modified: 2012/12/31 01:37 by aleksandar.mladenovic
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki