A minimálny kostrový strom (MST) je definovaný ako a kostra ktorý má minimálnu hmotnosť spomedzi všetkých možných kostrov

A kostra je definovaný ako stromový podgraf spojeného, ​​neorientovaného grafu, ktorý zahŕňa všetky vrcholy grafu. Alebo, laicky povedané, je to podmnožina hrán grafu, ktorá tvorí strom ( acyklický ), kde každý uzol grafu je súčasťou stromu.

Minimálny kostra má všetky vlastnosti kostry s dodatočným obmedzením, že má medzi všetkými možnými kostrami minimálnu možnú váhu. Podobne ako kostra, aj pre graf môže existovať veľa možných MST.

Vlastnosti kostry:

Kostra drží nižšie uvedené zásady :

• Počet vrcholov ( V ) v grafe a kostra je rovnaká.
• V kostre je pevný počet hrán, ktorý je o jednu menší ako celkový počet vrcholov ( A = V-1 ).
• Kostra by nemala byť odpojený , pretože v by mal byť iba jeden zdroj komponentu, nie viac ako to.
• Kostra by mala byť acyklický, ktoré znamená, že v strome nebude žiadny cyklus.
• Celková cena (alebo hmotnosť) kostry je definovaná ako súčet váh hrán všetkých hrán kostry.
• Pre graf môže existovať veľa možných kostry.

Minimálny kostrový strom:

A minimálny kostrový strom (MST) je definovaný ako a kostra ktorý má minimálnu hmotnosť spomedzi všetkých možných kostrov.

triedenie java arraylist

Minimálny kostra má všetky vlastnosti kostry s dodatočným obmedzením, že má medzi všetkými možnými kostrami minimálnu možnú váhu. Podobne ako kostra, aj pre graf môže existovať veľa možných MST.

• Pozrime sa na MST vyššie uvedeného príkladu grafu,
  

Minimálny kostra

Algoritmy na nájdenie minimálneho kostrového stromu:

Existuje niekoľko algoritmov na nájdenie minimálneho kostrového stromu z daného grafu, niektoré z nich sú uvedené nižšie:

odstránenie zo zoznamu polí

Kruskalov algoritmus minimálneho spanningového stromu:

Toto je jeden z populárnych algoritmov na nájdenie minimálneho kostry zo spojeného, ​​neorientovaného grafu. Toto je Najprv zoradí všetky okraje grafu podľa ich váh,

Tento algoritmus možno efektívne implementovať pomocou dátovej štruktúry DSU (Disjoint-Set) na sledovanie pripojených komponentov grafu. Používa sa v rôznych praktických aplikáciách, ako je návrh siete, klastrovanie a analýza údajov.

Postupujte podľa článku na Kruskalov algoritmus minimálneho spanningového stromu pre lepšie pochopenie a implementáciu algoritmu.

Postupujte podľa článku na Primov algoritmus minimálneho spanningového stromu pre lepšie pochopenie a implementáciu tohto algoritmu.

Borůvkov algoritmus minimálneho spanningového stromu:

Toto je tiež algoritmus prechodu grafu, ktorý sa používa na nájdenie minimálneho kostry spojeného, ​​neorientovaného grafu. Toto je jeden z najstarších algoritmov. Algoritmus funguje tak, že iteračne vytvára minimálny kostrový strom, pričom každý vrchol v grafe začína ako vlastný strom. V každej iterácii algoritmus nájde najlacnejšiu hranu, ktorá spája strom s iným stromom, a pridá túto hranu k minimálnemu kostre. Je to takmer podobné ako Primov algoritmus na nájdenie minimálneho kostry. Algoritmus má nasledujúci pracovný postup:

• Inicializujte les stromov, pričom každý vrchol v grafe má svoj vlastný strom.
• Pre každý strom v lese:
  • Nájdite najlacnejšiu hranu, ktorá ho spája s iným stromom. Pridajte tieto hrany do minimálneho kostry.
  • Aktualizujte les zlúčením stromov spojených pridanými okrajmi.
• Opakujte vyššie uvedené kroky, kým les nebude obsahovať iba jeden strom, čo je minimálny kostrový strom.

Algoritmus je možné implementovať pomocou dátovej štruktúry, ako je napríklad prioritný front, aby sa efektívne našla najlacnejšia hrana medzi stromami. Borůvkov algoritmus je jednoduchý a ľahko implementovateľný algoritmus na nájdenie minimálnych kostrových stromov, ale nemusí byť taký efektívny ako iné algoritmy pre veľké grafy s mnohými hranami.

Postupujte podľa článku na Boruvkov algoritmus minimálneho spanningového stromu pre lepšie pochopenie a implementáciu tohto algoritmu.

Ak sa chcete dozvedieť viac o vlastnostiach a charakteristikách Minimum Spanning Tree, kliknite tu.

Aplikácie minimálnych kostrových stromov:

• Návrh siete : Spanning trees je možné použiť pri návrhu siete na nájdenie minimálneho počtu spojení potrebných na prepojenie všetkých uzlov. Najmä minimálne kostry môžu pomôcť minimalizovať náklady na spoje výberom najlacnejších hrán.
• Spracovanie obrazu : Spanning trees možno použiť pri spracovaní obrazu na identifikáciu oblastí podobnej intenzity alebo farby, čo môže byť užitočné pri úlohách segmentácie a klasifikácie.
• Biológia : Kmenové stromy a stromy s minimálnym rozpätím možno použiť v biológii na konštrukciu fylogenetických stromov, ktoré reprezentujú evolučné vzťahy medzi druhmi alebo génmi.
• Analýza sociálnych sietí : Kmenové stromy a minimálne kostry možno použiť v analýze sociálnych sietí na identifikáciu dôležitých spojení a vzťahov medzi jednotlivcami alebo skupinami.

Niektoré populárne problémy s rozhovormi na MST

Niektoré často kladené otázky o minimálnom rozpätí stromov:

1. Môže existovať viacero stromov minimálneho rozpätia pre daný graf?

Áno, graf môže mať viacero minimálnych kostrov, ak existuje viacero sád hrán s rovnakou minimálnou celkovou hmotnosťou.

2. Môžu byť Kruskalov algoritmus a Primov algoritmus použité pre orientované grafy?

Nie, Kruskalov algoritmus a Primov algoritmus sú určené len pre neorientované grafy.

3. Môže mať odpojený graf minimálnu kostru?

Nie, odpojený graf nemôže mať kostru, pretože nezahŕňa všetky vrcholy. Preto tiež nemôže mať minimálny kostrový strom.

c pole reťazcov programu

4. Dá sa pomocou Dijkstrovho algoritmu nájsť minimálna kostra?

Nie, Dijkstrov algoritmus sa používa na nájdenie najkratšej cesty medzi dvoma vrcholmi vo váženom grafe. Nie je určený na nájdenie minimálneho kostry.

5. Aká je časová zložitosť Kruskalovho a Primovho algoritmu?

Kruskalov aj Primov algoritmus majú časovú zložitosť O(ElogE) , kde E je počet hrán v grafe.