A minimalus besitęsiantis medis (MST) apibrėžiamas kaip a besitęsiantis medis kuris turi mažiausią svorį tarp visų galimų besitęsiančių medžių
Atsitiktinių reikšmių generatorius java
A besitęsiantis medis apibrėžiamas kaip sujungto, neorientuoto grafo, apimančio visas grafo viršūnes, į medį panašus pografas. Arba, Laymano žodžiais tariant, tai yra grafiko kraštinių poaibis, kuris sudaro medį ( aciklinis ), kur kiekvienas grafiko mazgas yra medžio dalis.
Minimalus besitęsiantis medis turi visas besitęsiančio medžio savybes su papildomais apribojimais turėti mažiausią galimą visų galimų besitęsiančių medžių svorį. Kaip ir besitęsiantis medis, taip pat gali būti daug galimų grafiko MST.
Plintančio medžio savybės:
Aptampantis medis laiko žemiau minėtų principų :
- Viršūnių skaičius ( IN ) grafike ir apimantis medis yra toks pat.
- Apimančiame medyje yra fiksuotas briaunų skaičius, kuris yra vienu mažesnis už bendrą viršūnių skaičių ( IR = V-1 ).
- Aptampantis medis neturėtų būti atjungtas , nes turėtų būti tik vienas komponento šaltinis, bet ne daugiau.
- Aptampantis medis turi būti aciklinis, kurios reiškia, kad medyje nebūtų jokio ciklo.
- Bendra apimančio medžio kaina (arba svoris) apibrėžiama kaip visų besitęsiančio medžio kraštų kraštinių svorių suma.
- Grafike gali būti daug apimančių medžių.
Mažiausias besitęsiantis medis:
A minimalus besitęsiantis medis (MST) apibrėžiamas kaip a besitęsiantis medis kuris turi mažiausią svorį tarp visų galimų besitęsiančių medžių.
Minimalus besitęsiantis medis turi visas besitęsiančio medžio savybes su papildomais apribojimais turėti mažiausią galimą visų galimų besitęsiančių medžių svorį. Kaip ir besitęsiantis medis, taip pat gali būti daug galimų grafiko MST.
- Pažvelkime į aukščiau pateikto diagramos pavyzdžio MST,
Mažiausias besitęsiantis medis
Algoritmai, skirti rasti minimalų besitęsiantį medį:
Yra keli algoritmai, skirti rasti minimalų apimantį medį iš nurodyto grafiko, kai kurie iš jų yra išvardyti žemiau:
Kruskal minimalaus besitęsiančio medžio algoritmas:
Tai yra vienas iš populiariausių algoritmų, leidžiančių rasti minimalų apimantį medį iš prijungto, neorientuoto grafiko. Tai yra Pirma, jis surūšiuoja visas grafiko briaunas pagal jų svorį,
Šį algoritmą galima efektyviai įgyvendinti naudojant DSU (Disjoint-Set) duomenų struktūrą, kad būtų galima sekti prijungtus grafiko komponentus. Tai naudojama įvairiose praktinėse programose, tokiose kaip tinklo projektavimas, grupavimas ir duomenų analizė.
Sekite straipsnį Kruskalo minimalaus besitęsiančio medžio algoritmas Norėdami geriau suprasti ir įgyvendinti algoritmą.
Prim minimalaus besitęsiančio medžio algoritmas:
Tai taip pat gobšus algoritmas. Šis algoritmas turi tokią darbo eigą:
- Jis pradedamas pasirenkant savavališką viršūnę ir pridedant ją prie MST.
- Tada jis pakartotinai tikrina, ar nėra minimalaus krašto svorio, jungiančio vieną MST viršūnę su kita viršūne, kurios dar nėra MST.
- Šis procesas tęsiamas tol, kol visos viršūnės bus įtrauktos į MST.
Kad būtų galima efektyviai pasirinkti kiekvienos iteracijos minimalaus svorio kraštą, šis algoritmas naudoja priority_queue, kad išsaugotų viršūnes, surūšiuotas pagal jų minimalų kraštų svorį šiuo metu. Jis taip pat vienu metu seka MST naudodamas masyvą ar kitą duomenų struktūrą, tinkamą atsižvelgiant į saugomų duomenų tipą.
Šis algoritmas gali būti naudojamas įvairiuose scenarijuose, pvz., segmentuojant vaizdą pagal spalvą, tekstūrą ar kitas funkcijas. Maršrutizavimui, pavyzdžiui, ieškant trumpiausio kelio tarp dviejų pristatymo sunkvežimio taškų.
Sekite straipsnį Prim minimalaus besitęsiančio medžio algoritmas Norėdami geriau suprasti ir įgyvendinti šį algoritmą.
Boruvkos minimalaus besitęsiančio medžio algoritmas:
Tai taip pat yra grafiko apėjimo algoritmas, naudojamas norint rasti susieto, neorientuoto grafiko minimalų apimantį medį. Tai vienas iš seniausių algoritmų. Algoritmas veikia iteratyviai kurdamas minimalų apimantį medį, pradedant nuo kiekvienos grafiko viršūnės kaip atskiro medžio. Kiekvienoje iteracijoje algoritmas suranda pigiausią briauną, jungiančią medį su kitu medžiu, ir prideda tą kraštą prie minimalaus apimančio medžio. Tai beveik panašu į Prim algoritmą ieškant minimalaus besitęsiančio medžio. Algoritmas turi tokią darbo eigą:
- Inicijuokite medžių mišką, kiekvieną grafiko viršūnę nurodydami kaip atskirą medį.
- Kiekvienam medžiui miške:
- Raskite pigiausią kraštą, jungiantį jį su kitu medžiu. Pridėkite šiuos kraštus prie minimalaus besitęsiančio medžio.
- Atnaujinkite mišką sujungdami pridėtais kraštais sujungtus medžius.
- Kartokite aukščiau nurodytus veiksmus, kol miške bus tik vienas medis, kuris yra mažiausias besitęsiantis medis.
Algoritmas gali būti įgyvendintas naudojant duomenų struktūrą, pvz., prioritetinę eilę, kad būtų galima efektyviai rasti pigiausią kraštą tarp medžių. Boruvkos algoritmas yra paprastas ir lengvai įgyvendinamas algoritmas, skirtas rasti minimalius apimančius medžius, tačiau jis gali būti ne toks efektyvus kaip kiti algoritmai dideliems grafams su daug briaunų.
Sekite straipsnį Boruvkos minimalaus besitęsiančio medžio algoritmas Norėdami geriau suprasti ir įgyvendinti šį algoritmą.
Jei norite sužinoti daugiau apie minimalaus besitęsiančio medžio savybes ir charakteristikas, spustelėkite čia.
Mažiausiai besitęsiančių medžių pritaikymas:
- Tinklo projektavimas : Kuriant tinklą galima naudoti besitęsiančius medžius, kad būtų galima rasti mažiausią jungčių skaičių, reikalingą visiems mazgams sujungti. Ypač minimalūs besitęsiantys medžiai gali padėti sumažinti jungčių išlaidas, pasirenkant pigiausius kraštus.
- Vaizdo apdorojimas : apimantys medžius gali būti naudojami apdorojant vaizdus, kad būtų galima identifikuoti panašaus intensyvumo ar spalvos sritis, o tai gali būti naudinga atliekant segmentavimo ir klasifikavimo užduotis.
- Biologija : besitęsiantys medžiai ir mažiausiai besitęsiantys medžiai gali būti naudojami biologijoje konstruojant filogenetinius medžius, vaizduojančius evoliucinius rūšių ar genų ryšius.
- Socialinių tinklų analizė : apimantys medžius ir minimalius apimančius medžius gali būti naudojami socialinio tinklo analizėje, siekiant nustatyti svarbius asmenų ar grupių ryšius ir ryšius.
Kai kurios populiarios interviu problemos MST
| 1. | Raskite minimalią visų miestų sujungimo kainą | Praktika |
Kai kurie DUK apie minimalius besitęsiančius medžius:
1. Ar tam tikram grafikui gali būti keli minimalaus ilgio medžiai?
Taip, diagramoje gali būti keli minimalūs apimantys medžiai, jei yra keli briaunų rinkiniai, kurių minimalus bendras svoris.
2. Ar Kruskal algoritmas ir Primo algoritmas gali būti naudojami nukreiptiems grafams?
Ne, Kruskal algoritmas ir Primo algoritmas yra skirti tik neorientuotiems grafams.
3. Ar atjungtas grafikas gali turėti minimalų apimantį medį?
Ne, atjungtas grafikas negali turėti apimančio medžio, nes jis neapima visų viršūnių. Todėl jis taip pat negali turėti minimalaus besitęsiančio medžio.
4. Ar naudojant Dijkstra algoritmą galima rasti minimalų apimantį medį?
Ne, Dijkstros algoritmas naudojamas trumpiausiam keliui tarp dviejų svertinio grafiko viršūnių rasti. Jis nėra skirtas rasti minimalų besitęsiantį medį.
5. Koks yra Kruskalio ir Primo algoritmų sudėtingumas laikui bėgant?
Tiek Kruskal, tiek Prim algoritmai turi laiko sudėtingumą O (ElogE) , kur E yra kraštinių skaičius grafike.