A vähintään ulottuva puu (MST) määritellään a ylittävä puu jolla on pienin paino kaikista mahdollisista virittävistä puista

A ylittävä puu määritellään yhdistetyn, suuntaamattoman graafin puumaiseksi aligraafiksi, joka sisältää kaikki graafin kärjet. Tai, Laymanin sanoin, se on graafin reunojen osajoukko, joka muodostaa puun ( asyklinen ) jossa jokainen graafin solmu on osa puuta.

Vähimmäisvirittävällä puulla on kaikki virittävän puun ominaisuudet lisättynä rajoituksella, jonka mukaan kaikkien mahdollisten virittävien puiden painot ovat mahdollisimman pienet. Kuten virittävä puu, myös kaaviolla voi olla monia mahdollisia MST:itä.

Virtaavan puun ominaisuudet:

Virittävä puu pitää alla mainitut periaatteet :

• Huippupisteiden määrä ( SISÄÄN ) kaaviossa ja virittävä puu on sama.
• Virittävässä puussa on kiinteä määrä reunoja, joka on yhtä pienempi kuin pisteiden kokonaismäärä ( JA = V-1 ).
• Virittävä puu ei saa olla irti , koska siinä pitäisi olla vain yksi komponenttilähde, ei enempää.
• Ylittävän puun tulee olla asyklinen, joka tarkoittaa, että puussa ei olisi kiertoa.
• Virtaavan puun kokonaiskustannus (tai paino) määritellään virittävän puun kaikkien reunojen reunapainojen summana.
• Kaaviossa voi olla monia mahdollisia virittäviä puita.

Minimi virityspuu:

A vähintään ulottuva puu (MST) määritellään a ylittävä puu jolla on pienin paino kaikista mahdollisista virittävistä puista.

Vähimmäisvirittävällä puulla on kaikki virittävän puun ominaisuudet lisättynä rajoituksella, jonka mukaan kaikkien mahdollisten virittävien puiden painot ovat mahdollisimman pienet. Kuten virittävä puu, myös kaaviolla voi olla monia mahdollisia MST:itä.

• Katsotaanpa yllä olevan esimerkkikaavion MST:tä,
  

Vähintään virittävä puu

Näyttelijä Rubina Dilaik

Algoritmit vähimmäisvirityspuun löytämiseksi:

On olemassa useita algoritmeja minimivirittävän puun löytämiseksi tietystä kaaviosta, joista osa on lueteltu alla:

Kruskalin minimivirityspuualgoritmi:

Tämä on yksi suosituimmista algoritmeista minimivirittävän puun löytämiseksi yhdistetystä, suuntaamattomasta graafista. Tämä on Ensin se lajittelee kaikki kaavion reunat niiden painojen mukaan,

Tämä algoritmi voidaan toteuttaa tehokkaasti käyttämällä DSU (Disjoint-Set) -tietorakennetta graafin yhdistettyjen komponenttien seuraamiseen. Tätä käytetään useissa käytännön sovelluksissa, kuten verkkosuunnittelussa, klusteroinnissa ja tietojen analysoinnissa.

Seuraa artikkelia Kruskalin minimivirittävän puun algoritmi algoritmin ymmärtämiseksi ja toteuttamiseksi paremmin.

ydin java

• Se alkaa valitsemalla mielivaltainen kärkipiste ja lisäämällä se sitten MST:hen.
• Sitten se tarkistaa toistuvasti vähimmäisreunan painon, joka yhdistää yhden MST:n kärjen toiseen kärkeen, joka ei vielä ole MST:ssä.
• Tätä prosessia jatketaan, kunnes kaikki kärjet sisällytetään MST:hen.

Tämä algoritmi käyttää prioriteettijonoa valitakseen tehokkaasti kunkin iteroinnin vähimmäispainoreunan, joka tallentaa kärjet niiden nykyisen vähimmäispainon mukaan lajiteltuina. Se myös seuraa samanaikaisesti MST:tä käyttämällä taulukkoa tai muuta tietorakennetta, joka on sopiva sen tallennettavan tietotyypin mukaan.

Tätä algoritmia voidaan käyttää erilaisissa skenaarioissa, kuten kuvan segmentoinnissa värin, tekstuurin tai muiden ominaisuuksien perusteella. Reititystä varten, kuten lyhimmän reitin löytämisessä kahden pisteen välillä jakeluauton seurattavaksi.

Seuraa artikkelia Primin minimivirittävän puun algoritmi Tämän algoritmin ymmärtämiseksi ja toteuttamiseksi paremmin.

Boruvkan minimivirittävän puun algoritmi:

Tämä on myös graafin läpikulkualgoritmi, jota käytetään yhdistetyn, suuntaamattoman graafin vähimmäisvirittävän puun löytämiseen. Tämä on yksi vanhimmista algoritmeista. Algoritmi toimii iteratiivisesti rakentamalla minimivirittävän puun aloittaen jokaisesta graafin kärjestä omana puunaan. Jokaisessa iteraatiossa algoritmi löytää halvimman reunan, joka yhdistää puun toiseen puuhun, ja lisää tämän reunan minimivirittävän puun joukkoon. Tämä on melkein samanlainen kuin Primin algoritmi minimivirittävän puun löytämiseksi. Algoritmilla on seuraava työnkulku:

• Alusta puumetsä, jossa jokainen kaavion kärkipiste on oma puunsa.
• Jokaiselle metsän puulle:
  • Etsi halvin reuna, joka yhdistää sen toiseen puuhun. Lisää nämä reunat pienimpään virittävään puuhun.
  • Päivitä metsä yhdistämällä lisättyjen reunojen yhdistämät puut.
• Toista yllä olevia vaiheita, kunnes metsässä on vain yksi puu, joka on pienin virittävä puu.

Algoritmi voidaan toteuttaa käyttämällä tietorakennetta, kuten prioriteettijonoa, etsimään tehokkaasti halvin reuna puiden välillä. Boruvkan algoritmi on yksinkertainen ja helposti toteutettavissa oleva algoritmi minimivirittävän puiden etsimiseen, mutta se ei välttämättä ole yhtä tehokas kuin muut algoritmit suurille, monireunaisille graafille.

Seuraa artikkelia Boruvkan minimivirittävän puun algoritmi Tämän algoritmin ymmärtämiseksi ja toteuttamiseksi paremmin.

Saat lisätietoja Minimum Spanning Tree -puun ominaisuuksista napsauttamalla tässä.

Vähimmäisvirittävien puiden sovellukset:

• Verkon suunnittelu : Virtapuita voidaan käyttää verkon suunnittelussa kaikkien solmujen yhdistämiseen tarvittavien yhteyksien vähimmäismäärän löytämiseksi. Etenkin minimivirittävät puut voivat auttaa minimoimaan yhteyksien kustannuksia valitsemalla halvimmat reunat.
• Kuvankäsittely : Virtapuita voidaan käyttää kuvankäsittelyssä saman intensiteetin tai samanväristen alueiden tunnistamiseen, mikä voi olla hyödyllistä segmentointi- ja luokittelutehtävissä.
• Biologia : Virittäviä puita ja minimivirittäviä puita voidaan käyttää biologiassa fylogeneettisten puiden rakentamiseen edustamaan lajien tai geenien välisiä evoluutiosuhteita.
• Sosiaalisen verkoston analyysi : Virittäviä puita ja vähimmäisvirittäviä puita voidaan käyttää sosiaalisen verkoston analyysissä tärkeiden yhteyksien ja suhteiden tunnistamiseen yksilöiden tai ryhmien välillä.

Joitakin suosittuja haastatteluongelmia MST:ssä

Joitakin usein kysyttyjä kysymyksiä vähintään ulottuvista puista:

1. Voiko annetulle graafille olla useita minimivirittäviä puita?

Kyllä, kaaviossa voi olla useita vähimmäisvirittäviä puita, jos on useita reunajoukkoja, joilla on sama vähimmäiskokonaispaino.

2. Voidaanko Kruskalin algoritmia ja Primin algoritmia käyttää suunnatuille graafeille?

Ei, Kruskalin algoritmi ja Primin algoritmi on suunniteltu vain suuntaamattomille kaavioille.

3. Voiko katkonaisella graafilla olla pienin virittävä puu?

Ei, kytkemättömällä graafilla ei voi olla virittävää puuta, koska se ei kata kaikkia huippuja. Siksi sillä ei myöskään voi olla vähimmäisvirittävää puuta.

4. Löytyykö Dijkstran algoritmilla pienin virittävä puu?

Ei, Dijkstran algoritmia käytetään lyhimmän polun löytämiseen painotetun graafin kahden kärjen välillä. Sitä ei ole suunniteltu etsimään vähintään virittävää puuta.

5. Mikä on Kruskalin ja Primin algoritmien aikamonimutkaisuus?

Sekä Kruskalin että Primin algoritmeilla on aika monimutkaisuus O(ElogE) , jossa E on graafin reunojen lukumäärä.