Posted By: vik (Ninjas are mammals.) on 'CZprogram'
Title:     Re: Spojity graf
Date:      Wed Mar 27 17:36:22 2002

to vypada na prvni pohled jako obycejne prohledavani do sirky.

1. oznac vsechny vrcholy jako neoznacene.

2. vyber libovolny vrchol, oznac ho jako dosazeny
a dej ho do fronty

3. 
while (vrchol = popni zacatek fronty) {
   pridej na konec fronty nedosazene sousedy vrcholu a oznac je jako dosazene;
}

4. jestli je nejaky vrchol nedosazeny, graf je nesouvisly.


slozitost je o(|V| * max(grad(v))), kde 
|V| je pocet vrcholu grafu
a max (grad(v)) je maximalni stupen vrcholu.

doufam, ze je to spravne.
vik

Search the boards