Aprėpties medis: Skirtumas tarp puslapio versijų

Ištrintas turinys Pridėtas turinys
Tractor (aptarimas | indėlis)
Grąžinta atgal, Loading prašymu
Loading (aptarimas | indėlis)
SNėra keitimo santraukos
Eilutė 1:
'''Aprėpties medis''' tai jungaus neorientuoto [[Grafas (matematika)|grafo]] [[Medis (grafų teorija)|medis]], turintis visas to Grafo viršūnes.
#REDIRECT [[Medis (grafų teorija)]]
 
== Konstravimas ==
Du aprėpties medžio konstravimo algoritmai, remiasi anksčiau nagrinėtomis medžio apėjimo strategijomis: [[Grafas (duomenų sturūktūra)#paieška į gylį|paieškos į gylį]] (''DFS'') ir [[Grafas (duomenų sturūktūra)#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ę.
 
 
[[Category: Grafų teorija]]
[[Category: Duomenų struktūros]]
 
[[en:Spanning_tree]]