Aprėpties medis

Aprėpties medžio pavyzdys

Aprėpties medis tai jungaus neorientuoto grafo pografis, kuris yra medis, apimantis visas pradinio grafo viršūnes. Taigi, grafo ir jo aprėpties medžio viršūnių aibės sutampa, o grafo aprėpties medžio briaunų aibė yra tam tikras to grafo briaunų aibės poaibis.

Konstravimas

Du aprėpties medžio konstravimo algoritmai, remiasi skirtingomis grafo viršūnių apėjimo strategijomis: paieškos į gylį (DFS) ir paieškos į plotį (BFS). Bendru atveju šie algoritmai sukonstruos skirtingus aprėpties medžius, kuriuos toliau sąlyginai vadinsime DFS ir BFS aprėpties medžiais atitinkamai.

DFS aprėpties medis

Vienas iš būdų sukonstruoti aprėpties medį jungiam neorientuotam grafui yra apeiti grafo viršūnes, naudojant paieškos į gylį algoritmą. Apėjimo metu žymimos briaunos, kuriomis einama. Baigus apėjimą, pažymėtos briaunos sudarys paieškos į gylį aprėpties medį (DFS spanning tree). Tereikia nežymiai modifikuoti paieškos į gylį algoritmą (iteracinį ar rekursinį), kad apėjimo metu žymėtų briaunas.

BFS aprėpties medis

Kitas būdas sukonstruoti aprėpties medį jungiam neorientuotam grafui yra apeiti grafo viršūnes, naudojant paieškos į plotį algoritmą. Apėjimo metu žymimos briaunos, kuriomis einama. Baigus apėjimą, pažymėtos briaunos sudarys paieškos į plotį aprėpties medį (BFS spanning tree). Tam reikia modifikuoti paieškos į plotį algoritmą taip, kad jis pažymėtų briauną iš viršūnės W į viršūnę U, prieš pridėdamas viršūnę U į eilę.