Aprėpties medis
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Aprėpties medis tai duomenų struktūra, jungaus neorientuoto grafo medis, turintis visas to grafo viršūnes.
[taisyti] Konstravimas
Du aprėpties medžio konstravimo algoritmai, remiasi medžio apėjimo strategijomis: paieškos į gylį (DFS) ir paieška į 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.
[taisyti] 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
[taisyti] 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ę.