A minimālais stiepuma koks (MST) ir definēts kā a aptverošs koks kam ir minimālais svars starp visiem iespējamajiem aptverošajiem kokiem
A aptverošs koks ir definēts kā savienota, nevirzīta grafa kokam līdzīgs apakšgrāfs, kas ietver visas grafa virsotnes. Vai, sakot Layman vārdiem, tā ir grafika malu apakškopa, kas veido koku ( aciklisks ), kur katrs grafa mezgls ir koka daļa.
Minimālajam pārklājuma kokam ir visas stiepuma koka īpašības ar papildu ierobežojumu, ka visiem iespējamajiem stiepuma kokiem ir minimālais iespējamais svars. Tāpat kā aptverošam kokam, grafikam var būt arī daudz iespējamo MST.
Plaša koka īpašības:
Aptverošais koks notur zemāk minētie principi :
- Virsotņu skaits ( IN ) grafikā un aptverošais koks ir vienāds.
- Laišanas kokā ir noteikts šķautņu skaits, kas ir par vienu mazāks nekā kopējais virsotņu skaits ( UN = V-1 ).
- Aptvērējam kokam nevajadzētu būt atvienots , jo ir jābūt tikai vienam komponenta avotam, bet ne vairāk.
- Aptverošajam kokam jābūt aciklisks, kuras nozīmē, ka kokā nebūtu cikla.
- Aptverošā koka kopējās izmaksas (vai svars) tiek definētas kā visu stiepjošā koka malu malu svaru summa.
- Diagrammā var būt daudz iespējamo aptverošo koku.
Minimālais aptverošais koks:
A minimālais stiepuma koks (MST) ir definēts kā a aptverošs koks kam ir minimālais svars starp visiem iespējamajiem aptverošajiem kokiem.
Minimālajam pārklājuma kokam ir visas stiepuma koka īpašības ar papildu ierobežojumu, ka visiem iespējamajiem stiepuma kokiem ir minimālais iespējamais svars. Tāpat kā aptverošam kokam, grafikam var būt arī daudz iespējamo MST.
kas ir struktūra datu struktūrā
- Apskatīsim iepriekš minētā diagrammas piemēra MST,
Minimālais aptverošais koks
Algoritmi, lai atrastu minimālo aptverošo koku:
Ir vairāki algoritmi, lai atrastu minimālo aptverošo koku no noteiktā grafika, daži no tiem ir uzskaitīti zemāk:
Kruskal minimālā aptverošā koka algoritms:
Šis ir viens no populārākajiem algoritmiem, lai atrastu minimālo aptverošo koku no savienota, nevirzīta grafika. Tas ir Pirmkārt, tas sakārto visas diagrammas malas pēc to svara,
Šo algoritmu var efektīvi ieviest, izmantojot DSU (Disjoint-Set) datu struktūru, lai sekotu līdzi pievienotajiem grafika komponentiem. To izmanto dažādās praktiskās lietojumprogrammās, piemēram, tīkla projektēšanā, klasteru veidošanā un datu analīzē.
Sekojiet rakstam par Kruskal minimālā aptverošā koka algoritms lai labāk izprastu un ieviestu algoritmu.
Prim minimālā stiepuma koka algoritms:
Tas arī ir mantkārīgs algoritms. Šim algoritmam ir šāda darbplūsma:
- Tas sākas, izvēloties patvaļīgu virsotni un pēc tam pievienojot to MST.
- Pēc tam tas atkārtoti pārbauda minimālo malas svaru, kas savieno vienu MST virsotni ar citu virsotni, kas vēl nav MST.
- Šis process tiek turpināts, līdz visas virsotnes ir iekļautas MST.
Lai efektīvi atlasītu minimālā svara malu katrai iterācijai, šis algoritms izmanto priority_queue, lai saglabātu virsotnes, kas sakārtotas pēc to pašreizējās minimālās malas svara. Tas arī vienlaikus seko līdzi MST, izmantojot masīvu vai citu datu struktūru, kas ir piemērota, ņemot vērā datu tipu, ko tas glabā.
Šo algoritmu var izmantot dažādos scenārijos, piemēram, attēla segmentācijā, pamatojoties uz krāsu, tekstūru vai citām funkcijām. Maršrutēšanai, piemēram, lai atrastu īsāko ceļu starp diviem piegādes kravas automobiļa punktiem.
Sekojiet rakstam par Prima minimālā aptverošā koka algoritms lai labāk izprastu un ieviestu šo algoritmu.
Boruvkas minimālā aptverošā koka algoritms:
Šis ir arī grafika šķērsošanas algoritms, ko izmanto, lai atrastu savienota, nevirzīta grafika minimālo aptverošo koku. Šis ir viens no vecākajiem algoritmiem. Algoritms darbojas, iteratīvi veidojot minimālo aptverošo koku, sākot ar katru grafa virsotni kā savu koku. Katrā iterācijā algoritms atrod lētāko malu, kas savieno koku ar citu koku, un pievieno šo malu minimālajam aptverošajam kokam. Tas ir gandrīz līdzīgs Prim algoritmam minimālā aptverošā koka atrašanai. Algoritmam ir šāda darbplūsma:
- Inicializējiet koku mežu, katru grafa virsotni norādot kā savu koku.
- Katram kokam mežā:
- Atrodiet lētāko malu, kas savieno to ar citu koku. Pievienojiet šīs malas minimālajam stiepšanas kokam.
- Atjauniniet mežu, apvienojot kokus, kas savienoti ar pievienotajām malām.
- Atkārtojiet iepriekš minētās darbības, līdz mežā ir tikai viens koks, kas ir minimālais aptverošais koks.
Algoritmu var ieviest, izmantojot datu struktūru, piemēram, prioritāro rindu, lai efektīvi atrastu lētāko malu starp kokiem. Boruvkas algoritms ir vienkāršs un viegli īstenojams algoritms minimālo aptverošo koku atrašanai, taču tas var nebūt tik efektīvs kā citi algoritmi lieliem grafikiem ar daudzām malām.
Sekojiet rakstam par Boruvkas minimālā aptverošā koka algoritms lai labāk izprastu un ieviestu šo algoritmu.
Lai uzzinātu vairāk par minimālā aptverošā koka īpašībām un īpašībām, noklikšķiniet uz šeit.
Minimālo platuma koku pielietojumi:
- Tīkla dizains : aptverošus kokus var izmantot tīkla projektēšanā, lai atrastu minimālo savienojumu skaitu, kas nepieciešams visu mezglu savienošanai. Jo īpaši minimāli aptveroši koki var palīdzēt samazināt savienojumu izmaksas, izvēloties lētākās malas.
- Attēlu apstrāde : aptverošos kokus var izmantot attēlu apstrādē, lai identificētu līdzīgas intensitātes vai krāsas reģionus, kas var būt noderīgi segmentēšanas un klasifikācijas uzdevumos.
- Bioloģija : aptverošus kokus un minimāli aptverošus kokus var izmantot bioloģijā, lai izveidotu filoģenētiskus kokus, kas atspoguļo sugu vai gēnu evolūcijas attiecības.
- Sociālo tīklu analīze : Sociālo tīklu analīzē var izmantot aptverošos kokus un minimālos aptverošos kokus, lai noteiktu svarīgas saiknes un attiecības starp indivīdiem vai grupām.
Dažas populāras intervijas problēmas MST
| 1. | Atrodiet minimālās izmaksas, lai savienotu visas pilsētas | Prakse |
Daži bieži uzdotie jautājumi par minimālajiem platuma kokiem:
1. Vai dotajam grafikam var būt vairāki minimālā laiduma koki?
Jā, grafikā var būt vairāki minimāli aptverošie koki, ja ir vairākas malu kopas ar vienādu minimālo kopējo svaru.
2. Vai Kruskala algoritmu un Prima algoritmu var izmantot virzītiem grafiem?
Nē, Kruskal algoritms un Prim algoritms ir paredzēti tikai nevirzītiem grafikiem.
3. Vai atvienotam grafikam var būt minimālais aptverošais koks?
Nē, atvienotam grafam nevar būt aptverošs koks, jo tas neaptver visas virsotnes. Tāpēc tam nevar būt arī minimālais aptverošais koks.
Instagram priekšrocības personīgai lietošanai
4. Vai, izmantojot Dijkstra algoritmu, var atrast minimālo aptverošo koku?
Nē, Dijkstra algoritms tiek izmantots, lai atrastu īsāko ceļu starp divām virsotnēm svērtā grafikā. Tas nav paredzēts, lai atrastu minimālo platuma koku.
5. Kāda ir Kruskala un Prima algoritmu laika sarežģītība?
Gan Kruskal, gan Prim algoritmiem ir laika sarežģītība O(ElogE) , kur E ir grafa malu skaits.