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

Kitomis kalbomis