Primin MST keon avulla
Kasvata puuta yhdestä solmusta
Primin MST keon avulla on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Toinen tapa löytää MST
Prim's algorithm löytää myös minimum spanning tree -puun, mutta se kasvattaa yhtä yhtenäistä aluetta ulospäin sen sijaan, että kaikki kaaret lajiteltaisiin ensin. 🌱
Kasvattakaa puuta yhdestä solmusta
Valitkaa mikä tahansa aloitussolmu ja merkitkää se visited-tilaan. Puu alkaa yhdestä solmusta ja laajenee yksi kaari kerrallaan.
visited = [False] * nRintaman idea
Tarkastelkaa jokaisessa vaiheessa kaikkia kaaria, jotka kulkevat puusta sen ulkopuolelle. Prim's valitsee aina näistä rajalla olevista kaarista halvimman.
Keko valitsee pienimmän
Minimikeko tekee halvimman rajalla olevan kaaren löytämisestä nopeaa. Lisätkää ehdokaskaaret kekoon ja poistakaa pienimmän painon kaari jokaisella kierroksella.
import heapq
heap = [(0, start)]Poimikaa halvin kaari
Poistakaa keosta pienin alkio. Se antaa kaaren painon ja seuraavan solmun, joka voidaan liittää kasvavaan puuhun halvimmalla.
w, u = heapq.heappop(heap)Ohittakaa vanhentuneet alkiot
Solmu voi esiintyä keossa useammin kuin kerran. Jos poistamanne alkio viittaa solmuun, joka on jo visited-tilassa, ohittakaa se ja poistakaa seuraava alkio.
if visited[u]:
continueLisätkää ja laajentakaa
Merkitkää poistettu solmu visited-tilaan ja lisätkää sen paino kokonaissummaan. Lisätkää sitten kaikki sen lähtevät kaaret kekoon myöhempiä vaiheita varten.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Toistakaa, kunnes kaikki on mukana
Jatkakaa alkioiden poimimista ja puun laajentamista, kunnes jokainen solmu on visited-tilassa. Silloin kertynyt kokonaissumma on minimum spanning tree -puun paino.
Aikavaativuus
Jokainen kaari voidaan lisätä kekoon kerran ja poistaa sieltä kerran, joten kekoa käyttävä Prim's toimii ajassa O(E log V), joka on verrattavissa Kruskal's-algoritmiin.
Prim's ja Kruskal's
Käyttäkää Prim's-algoritmia tiheissä graafeissa, joissa on naapurustolista, ja Kruskal's-algoritmia, kun käytettävissänne on jo tavallinen kaarilista. Molemmat tuottavat saman MST-puun painon.
Se näyttää Dijkstran algoritmilta
Kekoa käyttävä silmukka muistuttaa Dijkstra's-algoritmia, mutta vertailkaa raakoja kaaripainoja, älkää polkujen etäisyyksiä. Tämän rakenteen tunnistaminen säästää koodausaikaa. ⚡
Pikatarkistus
Palauttakaa mieleenne, miten Prim's valitsee seuraavan kaaren kullakin kierroksella.
Kertaus
Kasvatitte MST-puun Prim's-algoritmilla: aloititte mistä tahansa, käytitte minimikekoa halvimman rajalla olevan kaaren lisäämiseen ja ohititte vanhentuneet käynnit. Hienoa työtä! 🎉
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Primin MST keon avulla” ilmainen?
Kyllä – oppitunnin ”Primin MST keon avulla” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Primin MST keon avulla”?
Kasvata puuta yhdestä solmusta Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.
Kuinka kauan ”Primin MST keon avulla”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- DSU polkujen pakkauksella
- Yhdistäminen rankin ja komponenttien perusteella
- Kruskalin pienin virittävä puu
- Primin MST keon avulla