ASD Ćwiczenia 11

Niech $G=(V,E)$ będzie grafem spójnym, a $w:E\to Z$ funkcją, która każdej krawędzi $e$ przypisuje nieujemą, całkowitoliczbową wagę $w(e)$. Dla każdego podgrafu $G^{\prime }=(V^{\prime },E^{\prime })$ definujemy wagę $W(G^{\prime })$ jako sumę wag jego krawędzi. Drzewo rozpinające grafu $G$, którego waga jest nie większa o od wagi każdego innego drzewa rozpinającego w tym grafie nazywamy minimalnym drzewem rozpinającym grafu $G$.

Wskazówka

Przedstaw za pomocą drzewa decyzyjnego algorytm sortowania przez scalanie z pominięciem zbędnych porównań.