DRZEWO

ROZPINAJĄCE

Zadanie: 

Graf nieskierowany :

1. Zbiór wierzchołek X = { x

1

, x

2

, ..., x

n

};

2. Zbiór krawędzi i ich wartość L = {l

1

, l

2

, ..., l

m

}.

 
Pobudować:

Drzewo Rozpinające

minimalne.  

Σ l

i

= min.

 

Algorytm  
1. Wybieramy dowolny pierwszy wierzchołek.
2. Wybieramy krawędź najmniejszej wartości.
3. Traktujemy utworzony fragment jak jeden wierzchołek.
4. Powracamy na Krok 2.

Kontrolujemy czy dodawana krawędź nie utworzy pętle

(cykl).

5. Koniec : Wszystkie wierzchołki są włączone w drzewo.