Aprėpties medis

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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